Здравствуйте! На acmp.ru есть задача о разрезании квадратного торта со свечками: необходимо определить, можно ли разрезать торт одним прямолинейным разрезом на две части равной площади так, чтобы все свечки оказались в одной половине. Задача с четвертьфинала Чемпионата мира Восточно-сибирского региона 2009 года.
Мое решение следующее:
Прямой разрез обязательно должен проходить через центр квадрата, поэтому масштабируем координаты точек в два раза, смещаем на сторону квадрата. После этой операции центр квадрата находится в центре координат. Если какая-то точка лежит в центре квадрата — ответ NO. Если всего одна точка — ответ YES.
Сортируем точки по полярному углу. Используя предикат
x > 0 || (x == 0 && y > 0)разбиваем множество всех точек на две части, каждую из которых сортируем в целых числах, затем склеиваем две части и дублируем первую точку в конец.Смотрим на знак векторного произведения соседних векторов. Если он отрицателен, то угол между векторами строго больше 180 градусов, следовательно можно провести разрез по прямой линии — ответ YES. Если ничего не подошло, ответ — NO.
Код выдает неправильный ответ на 9-м тесте.
