Здравствуйте! На acmp.ru есть задача о разрезании квадратного торта со свечками: необходимо определить, можно ли разрезать торт одним прямолинейным разрезом на две части равной площади так, чтобы все свечки оказались в одной половине. Задача с четвертьфинала Чемпионата мира Восточно-сибирского региона 2009 года.

Мое решение следующее:

1. Прямой разрез обязательно должен проходить через центр квадрата, поэтому масштабируем координаты точек в два раза, смещаем на сторону квадрата. После этой операции центр квадрата находится в центре координат. Если какая-то точка лежит в центре квадрата — ответ NO. Если всего одна точка — ответ YES.

2. Сортируем точки по полярному углу. Используя предикат x > 0 || (x == 0 && y > 0) разбиваем множество всех точек на две части, каждую из которых сортируем в целых числах, затем склеиваем две части и дублируем первую точку в конец.

3. Смотрим на знак векторного произведения соседних векторов. Если он отрицателен, то угол между векторами строго больше 180 градусов, следовательно можно провести разрез по прямой линии — ответ YES. Если ничего не подошло, ответ — NO.

Код выдает неправильный ответ на 9-м тесте.

UPD. Проблема решена. Контр-тест, который валит решение выше:

100
2
51 50
52 50

В данном случае после преобразования получаются векторы (2, 0) и (4, 0), которые имеют один и тот же полярный угол, их векторное произведение равно нулю, значит решение выдаст неверный ответ NO, а должно YES.

Исправить это просто: после сортировки нужно удалить повторяющиеся углы. Сделать это можно при помощи std::vector::erase и std::unique. Исправленное решение в целых числах, которое прошло все тесты.