Всем привет!

Хочу поделиться с вами решением задачи C, которое не использует вещественные числа вообще.

Идея та же самая: сортируем по углу с осью OX и пробегаемся по массиву.

1) Сортировка.

Разобьем наши вектора на два массива: y-координата неотрицательна и y-координата отрицательна. В первом массиве будем сортировать по возрастанию косинуса угла между вектором из массива и вектором с координатами (-1; 0). Во втором массиве будем сортировать по возрастанию косинуса угла между вектором из массива и вектором с координатами (1; 0). Сложим получившиеся массивы. Нетрудно увидеть, что мы отсортировали наши вектора по возрастанию угла с осью OX.

Как избавится от вещественного сравнения косинусов? Запишем скалярное произведение двумя способами:

cos(u, v) * |u| * |v| = u.x * v.x + u.y * v.y

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

2) Поиск ответа

Нам нужно найти два соседних вектора с наибольшим косинусом угла. Перебираем вектора i и i + 1 и сравниваем новый косинус с ответом. Опять возникает сравнение косинусов, но мы эту проблему решили выше :)

Стоит отметить, что при данных ограничениях 64-битным типом не обойтись, т.к. квадрат скалярного произведения векторов из входа может достигать 4 * 10 ^ 16, а квадраты длин векторов до 2 * 10 ^ 8

Код: 14262234