eolymp
bolt
Try our new interface for solving problems
Məsələlər

Üçbucaq islahat

Üçbucaq islahat

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Poliqoniya şahı IV Trianq islahat dəlisidir. Dünya tarixində qalmaq üçün o öz ölkəsində ərazi islahatı aparmaq qərarına gəldi. Poliqoniya ölkəsi sadə çoxbucaqlı formasındadır, yəni onun sərhəddi özünügəsmir və özünə toxunmur. Poliqoniyada dövlət sərhəddinin təpə nöqtələrini birləşdirən və sərhədlərə toxunmadan ölkənin ərazisindən keçən parçalar — daxili dioqanallar böyük rol oynayır. Bu zaman Poliqoniyanın forması elədir ki, heç bir iki daxili dioqanal eyni düz xətt üzərində yerləşmir.

Dövləti ənənəvi qaydada inzibati bölgələrə bölmək yerinə, şah IV Trianq öz ölkəsini daxili dioqanalları olan inzibatı üçbucaqlara bölmək qərarına gəldi. İdarəetmə aparatını ixtisara salmaq üçün şah ölkəni bölmək üçün elə plan hazırlamağı tapşırdı ki, inzibati üçbucaqların sayı minimum olsun.

Poliqoniyanı daxili dioqanallarla minimal sayda mümkün inzibati üçbucaqlara bölmə əməliyyatını icra edən proqramı yazmaq tələb olunur.

Giriş verilənləri

Giriş faylının birinci sətrində Poliqoniyanın sərhədlərini təşkil edən çoxbucaqlının təpələrinin sayını ifadə edən N (3N20) ədədi verilir. Növbəti N sətirin hər birində çoxbucaqlının saat əqrəbi istiqamətində dolaşma ardıcıllığında təpələrinin koordinatlarını ifadə edən mütləq qiymətcə 10000-i aşmayan 2 tam ədəd verilir. Zəmənət verilir ki, çoxbucaqlının heç bir üç ardıcıl gələn nöqtəsi bir düz xətt üzərində yerləşmir və onun özükəsişəni və özütoxunanı yoxdur. Həmçinin zəmanət verilir ki, çoxbucaqlının daxilində yerləşən heç bir iki dioqanal bir düz xətt üzərində yerləşmir.

Çıxış verilənləri

Çıxış faylının birinci sətrində Poliqoniyanın bölünməsi mümkün olan inzibati üçbucaqların minimal sayını verməli.

İkinci sətirdə bu bölgünün aparılmasını mümkün edən müxtəlif daxili dioqanalların K sayını verməli.

Hər bir növbəti K sətrində çoxbucaqlının daxilində tam yerləşən və onun sərhədlərindən keçməyən ayrılmış dioqanalların başlanşıc və son koordinatlarına uyğun 4 tam ədəd verin.

Əgər belə bölgü bir neçə olarsa, inlardan istənilən birini verin.

Nümunə

Giriş verilənləri #1
4
0 0
1 0
1 1
0 1
Çıxış verilənləri #1
2
1
1 1 0 0