Здравствуйте, друзья. По моей просьбе мой двоюродный брат, Сергей Зязюлькин, который проходит обучение на Факультете ФПМИ БГУ, написал одну из своих институтских задач и то, каким способом он её решил.
Задача
Корпорация «Русский алфавит» сделала новое прекрасное капиталовложение. Теперь во владении компании находится огромное поле плодородной земли, предназначенной для посева кукурузы. Поле имеет форму квадрата со стороной M метров. С давних времен на поле осталось N огромной высоты заборов, каждый из которых имеет форму отрезка ненулевой длины. Кроме того, в некоторой точке поля находится домик сторожа, в обязанности которого входит предотвращать кражу кукурузы.
Воровство кукурузы с полей в настоящее время приняло угрожающие масштабы. Поэтому сторожу вменено в обязанности постоянно следить за полем, предотвращая все попытки воровать собственность компании. К сожалению, сторож не может обозреть все кукурузное поле, потому что часть его скрыта за заборами.
Вы поступили на работу программистом в отдел развития и перспективных разработок. Ваше первое задание — подсчитать, какая часть кукурузного поля видна сторожу.
Входные данные
В первой строке входного файла записаны целые числа N и M (3 ≤ M ≤ 20000,0 ≤ N ≤ 20000). Следующая строка содержит пару чисел — координаты домика сторожа. Последующие N строк содержат по четыре числа x1, y1, x2, y2 – координаты концов каждого забора. Все координаты целые, противоположные углы поля имеют координаты соответственно (0, 0) и (M, M). Известно, что никакая пара заборов не имеет общих точек, кроме того, никакой забор не имеет общих точек с границей поля и с домиком сторожа. Забор можно считать отрезком нулевой ширины, а домик сторожа — точкой.
Известно, что домик сторожа не находится на границе поля.
Выходные данные
Выведите в выходной файл одно вещественное число не менее чем с 5 знаками после десятичной точки – видимую площадь поля.
Ограничение по времени: 3 сек.
Ограничение по памяти: 32 Мб
Пример
Ввод
1 5 1 4 1 2 3 4
Вывод
11.00000
Комментарии и решение
Обычная задача на хорошее знание геометрии и структур данных (бинарной кучи в частном). Задание сдавалось в олимпиадном стиле. Написал, отправил в систему, смотри результаты тестов.
Основной смысл в следующем: вводим систему координат Ox, Oy проходящую через точку наблюдателя (домик сторожа). Под углом точки понимаем угол между Ox и отрезком (домик сторожа – рассматриваемая точка). Угол отсчитываем против часовой стрелки от оси Ox.
- Считываем точки отрезков и заносим их в массив (точки сохраняем в структуры, определяющие какому отрезку она принадлежит, какой у нее угол, уравнение прямой проходящей через отрезок, концом которого является точка). Также заносим точки отрезков, являющихся границами поля (0,0), (0, M), (M, M), (M, 0), где M – размер поля.
- Сортируем эти точки по углу, от меньшего к большему.
- Создаем бинарную кучу, которая будет хранить на вершине ближайший к домику сторожа отрезок, заслоняющий часть поля, для данного сектора (сектор берется как две соседние точки в упорядоченном по возрастанию углов массиве).
- Делаем холостой пробег по всем точкам, чтобы определить вершину кучи для начального положения (для самой первой точки в массиве).
- Делаем второй пробег, определяя для каждого сектора ближайший отрезок и вычисляя видимую часть для данного сектора, по формуле площади треугольника.
Файл решения main.cpp
Архив с тестами tests_141.rar