Здравствуйте, друзья. По моей просьбе мой двоюродный брат, Сергей Зязюлькин, который проходит обучение на Факультете ФПМИ БГУ, написал одну из своих институтских задач и то, каким способом он её решил.

Задача

Корпорация «Русский алфавит» сделала новое прекрасное капиталовложение. Теперь во владении компании находится огромное поле плодородной земли, предназначенной для посева кукурузы. Поле имеет форму квадрата со стороной M метров. С давних времен на поле осталось N огромной высоты заборов, каждый из которых имеет форму отрезка ненулевой длины. Кроме того, в некоторой точке поля находится домик сторожа, в обязанности которого входит предотвращать кражу кукурузы.
Воровство кукурузы с полей в настоящее время приняло угрожающие масштабы. Поэтому сторожу вменено в обязанности постоянно следить за полем, предотвращая все попытки воровать собственность компании. К сожалению, сторож не может обозреть все кукурузное поле, потому что часть его скрыта за заборами.

Вы поступили на работу программистом в отдел развития и перспективных разработок. Ваше первое задание — подсчитать, какая часть кукурузного поля видна сторожу.

Входные данные
В первой строке входного файла записаны целые числа N и M (3 ≤ M ≤ 20000,0 ≤ N ≤ 20000). Следующая строка содержит пару чисел — координаты домика сторожа. Последующие N строк содержат по четыре числа x1, y1, x2, y2 – координаты концов каждого забора. Все координаты целые, противоположные углы поля имеют координаты соответственно (0, 0) и (M, M). Известно, что никакая пара заборов не имеет общих точек, кроме того, никакой забор не имеет общих точек с границей поля и с домиком сторожа. Забор можно считать отрезком нулевой ширины, а домик сторожа — точкой.

Известно, что домик сторожа не находится на границе поля.

Continue reading Задача по программированию 2й курс ФПМИ БГУ →