Олимпиадный тренинг

Задача . E. Дартс


Ночью после получения дипломов уже бывшие студенты German University in Cairo (GUC) играют в дартс. В отсутствие настоящей мишени ее роль успешно выполняют фотографии руководства университета.

На стене размещены n прямоугольных фотографий. Фотографии пересекаются различными способами. Некоторые из них оказались помещены на стену поверх других. Возможно даже, что несколько фотографий представлены одним и тем же прямоугольником. Фотографии не обязательно висят горизонтально и вертикально, они могут быть повернуты на произвольный угол.

Количество очков за один бросок равно количеству фотографий, которые проткнул дротик.

Фатма бросила дротик, но ее счет не был записан. Единственное, что она помнит — это то что ее дротик проткнул не менее одной фотографии.

В предположении, что плотность распределения вероятности попадания дротика одинакова по всей площади стены, какого среднее количество очков, которые должна получить Фатма?

Входные данные

На первой строке записано целое число n (1 ≤ n ≤ 500) — количество фотографий на стене. Последующие n строк задают фотографии. Каждая фотография задается 8 целыми числами (координатами 4 вершин прямоугольника): x1, y1, x2, y2, x3, y3, x4, y4.

Каждая фотография представляет собой прямоугольник ненулевой площади. Все координаты являются целыми числами, не превосходящими по модулю 104. Координаты вершин каждого прямоугольника заданы в порядке обхода этого прямоугольника по или против часовой стрелки.

Выходные данные

Выведите среднее количество очков за бросок. Ответ считается верным, если абсолютная или относительная погрешность не превосходит 10 - 6.


Примеры
Входные данныеВыходные данные
1 1
0 0 0 2 2 2 2 0
1.0000000000
2 1
-1 0 0 1 1 0 0 -1
1.0000000000
3 4
0 0 0 1 3 1 3 0
0 0 0 3 1 3 1 0
3 3 2 3 2 0 3 0
3 3 3 2 0 2 0 3
1.5000000000
4 2
-1 0 0 1 1 0 0 -1
0 0 1 1 2 0 1 -1
1.1428571429

time 5000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w645
Комментарий учителя