На сайте acmp.ru добавились 300 новых задач, и сейчас самое время их решить.
При решении задач на геометрию очень часто приходится рассматривать различные частные случаи, отлавливать подводные камни, и код от этого становится очень большим и некрасивым. Но в этой задаче удалось получить довольно неплохое решение.
Для начала создадим несколько функций, без которых не обходится почти ни одно решение задачи на геометрию: скалярное произведение векторов, косое произведение векторов и математическая функция sign, определяющая знак числа:
Данные считаем "как есть" и не будем их преобразовывать:
Замечание 1: чтобы квадрат поделить на две равные по площади части надо разрез проводить через его центр - точку пересечения диагоналей.
Замечание 2: если нужный нам разрез существует, то существует и подходящий нам разрез, проходящий сколь угодно близко к одной из свечек. Это легко представить, взяв правильный разрез и поворачивать его до тех пор пока не упрёмся в свечку.
Отсюда получаем идею решения: надо проверить все разрезы, соединяющие одну из свечек и центр квадрата (всего 100 штук) и для каждого разреза посчитать, сколько свечек слева от него - c[1], справа от него - c[-1], на нём в сторону выбранной свечи (относительно центра) - c0[1], на нём в сторону от выбранной свечи - c0[-1]. Всё это делается с помощью композиции косого и скалярного произведений. А функция sign применяется для удобства работы с индексами.
Вроде даже не такое ужасное решение.
Я очень хочу, чтобы мои советы были полезны вам, а для того, чтобы быстрее всех получать новые статьи можно подписаться на мой канал.