1207. Медиана

На плоскости задано n точек (n четно). Никакие три точки не лежат на одной прямой. Необходимо найти такие две точки, что прямая, проведенная через них, разобьет исходное множество точек на две равные по количеству части.

Вход. Первая строка содержит количество точек n (2 £ n £ 10000) на плоскости. Следующие n строк описывают координаты точек x_i, y_i (-10⁹ < x_i, y_i < 10⁹, 1 £ i £ n).

Выход. Номера искомых двух точек. Точки нумеруются с единицы.

Пример входа

4

0 0

1 0

0 1

1 1

Пример выхода

1 4

РЕШЕНИЕ

геометрия

Анализ алгоритма

Найдем точку P с минимальной ординатой. Сделаем параллельный перенос, перенеся в P начало координат. Все множество точек после этого будет лежать не ниже оси абсцисс. Отсортируем все точки кроме P по полярному углу. Пусть P₁, P₂, …, P_n-1 – полученное множество отсортированных точек. Тогда искомыми двумя точками будут P и P_n/2.

Реализация алгоритма

Координаты входных точек будем хранить в массиве v структур point.

struct point{

int x,y,id;

} v[10001];

При сортировке точек по полярному углу будем использовать функцию f. Известно, что вектор OA образует больший угол с осью абсцисс, нежели OB (точка О – начало координат), если выполняется одно из следующих условий:

а) y₁ < 0, y₂ ³ 0; б) y₂ = 0, x₁ > 0; в) OA ´ OB < 0;

Первое условие никогда не будет выполняться, так как все точки лежат не ниже оси абсцисс. Поэтому достаточно реализовать в функции f два последних условия. Функции сравнения f в качестве аргументов передаются две точки x и y. Пусть A(x.x,x.y), B(y.x,y.y), тогда

OA ´ OB = = x.x * y.y – x.y * y.x

Неравенство OA ´ OB < 0 можно переписать в виде x.x * y.y < x.y * y.x. Поскольку -10⁹ < x_i, y_i < 10⁹, то при перемножении координат может возникнуть переполнение. Поэтому при вычислении векторного произведения следует преобразовать числа в тип __int64.

int f(struct point x, struct point y)

{

if ((x.x > 0) && (y.y == 0)) return 1;

if ((__int64)x.x * y.y < (__int64)x.y * y.x) return 1;

return 0;

}

Основной цикл программы. Переменная miny будет содержать наименьшую ординату точки, p – ее номер. Изначально положим miny равным максимально возможному числу. Читаем координаты точек, заносим их в массив v и параллельно ищем точку с наименьшей ординатой.

int p,miny = 2000000000;

scanf("%d",&n);

for(i=0;i<n;i++)

{

scanf("%d %d",&v[i].x,&v[i].y); v[i].id = i+1;

if (v[i].y < miny) {miny = v[i].y; p = i;}

}

Поменяем местами нулевую и p - ую точку. Вычтем из координат всех точек координаты нулевой точки, таким образом совершив параллельный перенос точки с наименьшей ординатой в начало координат.

swap(v[0],v[p]);

for(i=1;i<n;i++) v[i].x -= v[0].x,v[i].y -= v[0].y;

Сортируем точки с первой до n - ой. Нулевую точку не трогаем, она имеет координаты (0, 0). Выводим номера искомых точек. Поскольку в Си нумерация точек идет с нуля, а по условию задачи их нумеровать следует с 1, то выводить следует номер p + 1.

sort(v+1,v+n,f);

printf("%d %d\n",p+1,v[n/2].id);