Замечание: Время на тест и ограничени по памяти для этой задачи
3 секунды и 512MB, что в 1.5 и 2 раза соответственно больше значений
по умолчанию.**
Каждая из \(N\) коров (\(1 \leq N \leq 10^5\)) Фермера Джона любит ежедневно
гулять вдоль изгороди, окружающей пастбище. К несчастью, когда корова проходит
столб, она задевает его, что заставляет ФД регулярно перекрашивать столбы
изгороди.
Изгородь состоит из \(P\) столбов (\(4 \leq P \leq 2\cdot 10^5\), \(P\) четное),
с различными координатами \((x,y)\) на плоскости (\(0 \leq x, y \leq 10^9\)).
Каждый столб связан с двумя соседними столбами забором, который представляет
собой вертикальный или горизонтальный отрезок прямой. Поэтому вся изгородь
может рассматриваться как многоугольник со сторонами, паралельными осям x и y.
Последний столб соединён с первым столбом, поэтому изгородь представляет собой
замкнутую ломаную. Многоугольник изгороди таков, что отрезки изгороди
пересекаются только в конечных точках, каждый столб является конечной точкой
ровно двух отрезков, и каждый два отрезка, которые имеют общую конечную точку
перпендикулярны.
Каждая корова имеет предпочитаемые стартовую и конечную позиции своей
прогулки. Каждая позиция расположена на изгороди, возможно в столбе, а
возможно и нет. Имеется два маршрута, по которым корова может пройти из
стартовой позиции в конечную, поскольку многоугольник замкнутый. Коровы
ленивы и потому пойдут в том направлении, в котором расстояние от стартовой
точки до конечно меньше. Гарантируется, что равенства быть не может.
Корова касается столба изгороди, когда проходит его, или если этот столб
является стартовой или конечной точкой её прогулки. Помогите ФД вычислить
количество ежедневных касаний каждого столба изгороди, чтобы он знал какой
столб перекрашивать следующим.
Можно показать, что существует единственная изгородь, если заданы
координаты всех её столбов.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка ввода содержит \(N\) и \(P\). Каждая из последующих \(P\) строк
содержит два целых числа, представляющих позиции столбов изгороди в неизвестном
порядке. Каждая из последующих \(N\) строк содержит четыре целых числа
\(x_1\) \(y_1\), \(x_2\) \(y_2\) представляющих стартовую позицию \((x_1, y_1)\)
и конечную позицию \((x_2, y_2)\) коровы.
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(P\) целых чисел, количества касаний каждого из столбов изгороди.
SCORING:
- Тесты 4-6: \(N,P\le 1000\)
- Тесты 7-9: Все координаты соответствуют условиям \(0\le x, y\le 1000\).
- Тесты 10-15: Нет дополнительных ограничений.