Задачі
Трикутна реформа
Трикутна реформа
Король Полігонії Тріанг IV помішаний на реформах. Щоб увійти у світову історію, він вирішив провести територіальну реформу у своії країні. Крїана Полігонія має форму простого многокутника, тобто її границя не має самоперетинів та самодотикань. У Полігонії велику роль відіграють \textit{внутрішні діагоналі} --- відрізки, які з'єднують вершини державного кордону і які повністю проходять по території країни, не дотикаючись границь. При цьому форма Полігонії така, що ніякі дві внутрішні діагоналі не лежать на одній прямій.
Замість традиційного поділу держави на \textit{адміністративні одиниці} король Тріанг IV вирішив розділити свою країну на \textit{адміністративні трикутники} внутрішніми діагоналями. Для скорочення адміністративного апарату король звелів підготувати такий план поділу країни, у якому кількість адміністративних трикутників буде мінімальною.
Потрібно написати програму, яка виконує поділ Полігонії внутрішніми діагоналями на мінімально можливе число адміністративних трикутників.
\InputFile
У першому рядку вхідного файлу записано число \textbf{N} (\textbf{3} ≤ \textbf{N} ≤ \textbf{20}) --- кількість вершин многокутника, який утворює границю Полігонії. У наступних \textbf{N} рядках знаходяться по \textbf{2} цілих числа, які за абсолютною величиною не перевищують \textbf{10000} --- координати вершин у порядку обходу многокутника проти годинникової стрілки. Гарантується, що ніякі три послідовні вершини многокутника не лежать на одній прямій, і він не має самоперетинів та самодотикань. Також гарантується, що ніякі дві діагоналі, що містяться всередині многокутника, не лежать на одній прямій.
\OutputFile
У перший рядок вихідного файлу виведіть найменшу кількість адміністративних трикутників, на які можна розбити Полігонію.
У другому рядку виведіть кількість різних внутрішніх діагоналей \textbf{K}, при допомозі яких можна здійснити дане разбиття.
У кожен з наступнх \textbf{K} рядків виведіть \textbf{4} цілих числа --- координати початку та кінця відповідної діагоналі розбиття, яке повністю лежить всередині многокутника і не проходить по його границі.
Якщо шуканих разбиттів декілька, виведіть довільне з них.
Вхідні дані #1
4 0 0 1 0 1 1 0 1
Вихідні дані #1
2 1 1 1 0 0