Задача №112334. Коллайдер 2.0
На детектор сверху направлена сверхскоростная камера на вращающемся в горизонтальной плоскости креплении. Ориентация камеры в каждый момент времени задаётся направляющей прямой. Камера может сфотографировать произвольную прямоугольную область, одна из сторон которой параллельна заданной направляющей прямой
Для анализа потенциальных столкновений частиц важно, чтобы на каждом фотоснимке были отображены все точки пересечений их траекторий. Камера использует очень дорогие расходные материалы, поэтому площадь каждого фотоснимка необходимо минимизировать.
Требуется написать программу, которая по хронологической последовательности событий двух типов:
• появление новой траектории частицы,
• получение фотоснимка камерой, ориентированной по заданной направляющей прямой,
определит для каждого фотоснимка минимальную площадь прямоугольной области, включающей все точки пересечения траекторий частиц, появившихся до этого снимка.
В первой строке входного файла задано одно целое число n (1 <= \(n\) <= 200 000) — общее количество событий. В следующих \(n\) строках заданы описания событий.
Описание каждого события состоит из пяти элементов. Первый элемент является символом «+», если это событие является появлением новой траектории, или символом «?», если это событие является получением фотоснимка. Последующие четыре элемента — целые числа \(x_1\), \(y_1\), \(x_2\), \(y_2\) (−10 000 <= \(x_1\), \(y_1\), \(x_2\), \(y_2\) <= 10 000) — координаты двух несовпадающих точек. Для событий первого типа указанные точки лежат на траектории частицы. Все траектории различны. Для событий второго типа указанные точки лежат на направляющей прямой камеры.
Пусть \(q\) — количество полученных фотоснимков. Выходной файл должен содержать \(q\) вещественных чисел — минимальные возможные площади фотоснимков, перечисленные в порядке их получения камерой.Тест будет успешно пройден, если для каждой из \(q\) выведенных площадей выполняется условие |a - b| / (max(1, b)) <= 10-4, где \(a\) — площадь, выведенная участником, \(b\) — площадь, полученная решением жюри.
Далее приведены рисунки для первого и второго примеров соответственно.
Для проверки решений этой задачи используются 50 тестов. Тесты оцениваются независимо. Каждый тест оценивается в 2 балла. Значения \(n\) и \(q\), а также некоторые характеристики тестов приведены в таблице.
| Тест | n | q | Примечание |
| 1. | 10 | 1 | Направляющие прямые параллельны осям координат |
| 2. | 20 | 10 | Направляющие прямые параллельны осям координат |
| 3. | 745 | 365 | Направляющие прямые параллельны осям координат |
| 4. | 1997 | 10 | Направляющие прямые параллельны осям координат |
| 5. | 2000 | 1000 | Направляющие прямые параллельны осям координат |
| 6. | 100001 | 1 | Направляющие прямые параллельны осям координат |
| 7. | 100002 | 1 | Направляющие прямые параллельны осям координат |
| 8. | 200000 | 1 | Направляющие прямые параллельны осям координат |
| 9. | 200000 | 100000 | Направляющие прямые параллельны осям координат |
| 10. | 200000 | 130000 | Направляющие прямые параллельны осям координат |
| 11. | 1000 | 10 | |
| 12. | 500 | 250 | |
| 13. | 10100 | 10000 | |
| 14. | 700 | 100 | |
| 15. | 800 | 71 | |
| 16. | 2001 | 1000 | |
| 17. | 5003 | 2000 | |
| 18. | 7005 | 4000 | |
| 19. | 8007 | 1000 | |
| 20. | 9009 | 4500 | |
| 21. | 90100 | 90001 | |
| 22. | 5000 | 101 | |
| 23. | 6000 | 98 | |
| 24. | 5432 | 2345 | |
| 25. | 9508 | 4079 | |
| 26. | 156002 | 151001 | Все фотоснимки выполняются после появления всех частиц |
| 27. | 157004 | 152001 | Все фотоснимки выполняются после появления всех частиц |
| 28. | 197062 | 190001 | Все фотоснимки выполняются после появления всех частиц |
| 29. | 148008 | 141001 | Все фотоснимки выполняются после появления всех частиц |
| 30. | 169010 | 163501 | Все фотоснимки выполняются после появления всех частиц |
| 31. | 165011 | 159001 | Все фотоснимки выполняются после появления всех частиц |
| 32. | 185001 | 179102 | Все фотоснимки выполняются после появления всех частиц |
| 33. | 176001 | 168098 | Все фотоснимки выполняются после появления всех частиц |
| 34. | 155433 | 147234 | Все фотоснимки выполняются после появления всех частиц |
| 35. | 159608 | 152179 | Все фотоснимки выполняются после появления всех частиц |
| 36. | 165011 | 159001 | |
| 37. | 185001 | 179102 | |
| 38. | 176001 | 174000 | |
| 39. | 155433 | 153556 | |
| 40. | 159608 | 157701 | |
| 41. | 200000 | 1 | |
| 42. | 110000 | 10 | |
| 43. | 120000 | 50 | |
| 44. | 199999 | 70 | |
| 45. | 188888 | 100 | |
| 46. | 200000 | 100000 | |
| 47. | 199999 | 195000 | |
| 48. | 199999 | 100000 | |
| 49. | 178689 | 98276 | |
| 50. | 199998 | 88888 |
6 + 0 0 0 1 + 0 0 1 0 + 1 0 0 2 ? 0 0 0 1 + 2 4 3 6 ? 0 0 1 1
2.0 3.000
7 ? 11 4 -7 8 + -2 -2 1 1 ? 0 0 0 1 + 0 1 1 0 + 0 2 2 0 ? 0 0 0 1 ? 0 0 1 1
0.0 0.0 0.25 0.0000000