reform. in | |
Имя выходного файла: | reform. out |
Максимальное время работы на одном тесте: | 2 секунда |
Максимальный объем используемой памяти: | 64 мегабайта |
Максимальная оценка | 100 баллов |
Король Полигонии Трианг IV помешан на реформах. Чтобы войти в мировую историю, он решил провести территориальную реформу в своей стране. Страна Полигония имеет форму простого многоугольника, то есть ее граница не имеет самопересечений и самокасаний. В Полигонии большую роль играют внутренние диагонали — отрезки, соединяющие вершины государственной границы и полностью проходящие по территории страны, не касаясь границы. При этом форма Полигонии такова, что никакие две внутренние диагонали не лежат на одной прямой.
Вместо традиционного деления государства на административные округа король Трианг IV решил разделить свою страну на административные треугольники внутренними диагоналями. Для сокращения управляющего аппарата король повелел подготовить такой план деления страны, в котором количество административных треугольников будет минимальным.
Требуется написать программу, выполняющую деление Полигонии внутренними диагоналями на минимально возможное число административных треугольников.
Формат входных данных
В первой строке входного файла записано число N — количество вершин многоугольника, образующего границу Полигонии. В следующих N строках находятся по 2 целых числа, по абсолютной величине не превосходящие 10 000 — координаты вершин в порядке обхода многоугольника против часовой стрелки. Гарантируется, что никакие три последовательные вершины многоугольника не лежат на одной прямой, и он не имеет самопересечений и самокасаний. Также гарантируется, что никакие две диагонали, содержащиеся внутри многоугольника, не лежат на одной прямой.
Формат выходных данных
В первую строку выходного файла выведите наименьшее количество административных треугольников, на которое можно разбить Полигонию.
Во вторую строку выведите количество различных внутренних диагоналей K, с помощью которых можно произвести данное разбиение.
В каждую из следующих K строк выведите 4 целых числа — координаты начала и конца соответствующей диагонали разбиения, полностью лежащей внутри многоугольника и не проходящей по его границе.
Если искомых разбиений несколько, выведите любое из них.
Примеры
reform. in | reform. out | Рисунок к тесту |
4 0 0 1 0 1 1 0 1 | 2 1 1 1 0 0 |
|
10 -6 0 0 2 6 0 3 3 6 4 2 4 0 6 -2 4 -6 4 -3 3 | 4 3 2 4 -2 4 0 2 3 3 -3 3 0 2 |
|
Подзадачи и система оценки
Данная задача содержит три подзадачи.
Подзадача 1 (10 баллов)
3 ≤ N ≤ 4.
Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
Подзадача 2 (15 баллов)
3 ≤ N ≤ 10.
Для оценки данной подзадачи используется соответствующая группа тестов. Баллы за подзадачу начисляются только в том случае, если все тесты из этой группы пройдены.
Подзадача 3 (75 баллов)
3 ≤ N ≤ 20.
Каждый тест для данной подзадачи оценивается отдельно.
Обратная связь
В течение тура можно не более 10 раз запросить баллы, которые набирает программа на тестах жюри. Запрос можно делать не чаще одного раза в 5 минут. Для каждой подзадачи сообщаются результаты проверки на каждом тесте.
В этой задаче можно выбрать, какое решение будет оцениваться. В этом случае баллы начисляются за лучшее решение из следующих:
- выбранного явно; последнего принятого на проверку решения.
Если выбор не сделан, то будет оцениваться лучшее решение из следующих:
- тех решений, по которым просмотрены баллы; последнего принятого на проверку решения.
