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