Всем привет!
Хочу поделиться с вами решением задачи 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
Спасибо. В своем разборе http://codeforces.net/blog/entry/21590 я написал как обойтись 64-битным типом данных. Использование псевдовекторных произведений лучше согласуется с определением направлений.