ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1207. Медиана на плоскости

Why wrong answer?
Послано Grigorenko Vlad 16 июн 2013 17:17
using System;

class point{
    public int x, y, id;
}

class EntryPoint
{
    static void Main()
    {
        point[] v=new point [10001];
        int n = Convert.ToInt32(Console.ReadLine());
        int min_i=0;
        int min = 20000000;
        for (int i = 0; i < n; i++)
        {
            v[i] = new point();
            string[] str = Console.ReadLine().Split(' ');
            v[i].x = Convert.ToInt32(str[0]);
            v[i].y = Convert.ToInt32(str[1]);
            v[i].id = i+1;
            if (v[i].y < min)
            {
                min = v[i].y;
                min_i = i;
            }
        }
        swap(ref v[0], ref v[min_i]);
        for (int i = 0; i < n; i++)
        {
            v[i].x -= v[i].x;
            v[i].y -= v[i].y;
        }
        fast_sort(v,0,n-1);
        Console.WriteLine(min_i+1+" "+v[n/2+1].id);
    }

    static int fync(point a, point b)
    {
        if ((a.x > 0) && (b.y == 0)) return 1;
        if (a.x * b.y < a.y * b.x) return 1;
        return 0;
    }
    static void swap(ref point a, ref point b)
    {
        point tmp;
        tmp = a;
        a = b;
        b = a;
    }
    static void fast_sort(point[] arr,int low,int high)
    {
        int i,j;
        int x;
        i = low;
        j = high;
        x = arr[(i + j) / 2].y;
        do
        {
            while (arr[i].y < x) ++i;
            while (arr[j].y > x) --j;
            if (i <= j)
            {
                int temp = arr[i].y;
                arr[i].y = arr[j].y;
                arr[j].y = temp;
                i++; j--;
            }
        } while (i <= j);
        if (low < j) fast_sort(arr,
            low, j);
        if (i < high) fast_sort(arr, i, high);
    }
}