Daugiakampis

UŽDUOTIS

Daugiakampį sudaro visi taškai, esantys jo viduje ir ant jį ribojančios linijos. Iškilusis daugiakampis yra toks, kai bet kuriuos du jo taškus X ir Y jungianti atkarpa visa priklauso tam daugiakampiui. Šiame uždavinyje nagrinėsime tik iškiliuosius daugiakampius, turinčius mažiausiai dvi viršūnes. Visos viršūnės yra skirtingos ir jų koordinatės yra sveikieji skaičiai. Jokios trys viršūnės nėra kolinearios.

Duoti du daugiakampiai A ir B. Jų Minkovskio sumą sudaro visi taškai, kurių koordinatės yra pavidalo (x1+x2, y1+y2), čia (x1, y1) priklauso daugiakampiui A, o (x2, y2) – daugiakampiui B. Žinoma, kad Minkovskio suma vėl yra daugiakampis. Pavyzdyje pateikti du trikampiai ir jų Minkovskio suma. 

Panagrinėkime operaciją, atvirkštinę Minkovsko sumai. Duotam daugiakampiui P reikia rasti du tokius daugiakampius A ir B, kad:
-	P būtų daugiakampių A ir B Minkovskio suma,  
-	A turėtų nuo 2 iki 4 skirtingų viršūnių, t. y. būtų arba atkarpa (2 viršūnės), arba trikampis (3 viršūnės), arba keturkampis (4 viršūnės), 
-	A turėtų kiek galima daugiau viršūnių, būtent:
•	A turi būti keturkampis (jei tik galima), 
•	jei A negali būti keturkampis, tai turi būti trikampis (jei tik galima), 
•	priešingu atveju A turi būti atkarpa. 

Suprantama, nei vienas iš daugiakampių A arba B negali būti lygus P, nes tuomet kitas dėmuo turėtų būti taškas (o tai nėra daugiakampis).

Duotas rinkinys pradinių bylų, kurių kiekviena aprašo daugiakampį P. Kiekvienai pradinių duomenų bylai reikia rasti daugiakampius A ir B, kurie tenkintų aprašytus reikalavimus, ir sukurti rezultatų bylą su šių daugiakampių A ir B aprašais. Žinoma, kad duotiems duomenims visuomet galima rasti sprendinį (reikalaujamus daugiakampius A ir B). Jei yra daugiau sprendinių, reikia rasti ir pateikti vieną iš jų. Nereikia pateikti programos, tik rezultatų bylas. 

PRADINIAI DUOMENYS

Duota 10 tekstinių bylų, pavadintų polygon1.in, ... polygon10.in; skaičius varde nurodo pradinių duomenų bylos numerį. Kiekviena pradinių duomenų byla yra šitokio pavidalo. Pirmoje bylos eilutėje įrašytas vienas sveikasis skaičius N: daugiakampio P viršūnių skaičius. Likusios N eilučių aprašo viršūnes prieš laikrodžio rodyklę: vienai viršūnei skiriama viena eilutė. I+1-ojoje eilutėje (I = 1, 2, ..., N) įrašyti du sveikieji tarpu atskirti skaičiai XI ir YI: tai I-tosios daugiakampio viršūnės koordinatės. Visos koordinatės yra neneigiami sveikieji skaičiai.

REZULTATAI

Duotoms pradinių duomenų byloms turite pateikti 10 rezultatų bylų, kurios aprašytų rastuosius daugiakampius A ir B. Pirmoje eilutėje turi būti tekstas:
#FILE polygon I
čia sveikasis skaičius I (1≤I≤10) yra atitinkamos pradinių duomenų bylos numeris.

Rezultatų bylos formatas panašus į pradinių duomenų bylos. Antroje eilutėje turi būti vienas sveikasis skaičius NA: daugiakampio A viršūnių skaičius (2≤NA≤4). Likusios NA eilučių aprašo daugiakampio A viršūnes prieš laikrodžio rodyklę: vienai viršūnei skiriama viena eilutė. I+2-ojoje eilutėje (I = 1, 2, ..., NA) įrašyti du sveikieji tarpu atskirti skaičiai X ir Y: tai I-tosios daugiakampio A viršūnės koordinatės. 

NA+3-ojoje eilutėje turi būti vienas sveikasis skaičius NB: daugiakampio B viršūnių skaičius, (2≤NB). Likusios NB eilučių aprašo daugiakampio B viršūnes prieš laikrodžio rodyklę: vienai viršūnei skiriama viena eilutė. NA+J+3-ojoje eilutėje (J = 1, 2, ..., NB) įrašyti du tarpu atskirti sveikieji skaičiai X ir Y: tai J-tosios daugiakampio B viršūnės koordinatės. 

PAVYZDYS

polygon0.in		

5
0 1
0 0
2 0
2 1
1 2

				

Duotai pradinių duomenų bylai bet kuris iš pateiktų rezultatų yra teisingas sprendinys (žiūrėkite paveikslus), kadangi abiem atvejais A yra trikampis ir negali būti keturkampis. 

#FILE polygon 0
3
0 0
1 0
1 1
3
0 1
0 0
1 0

#FILE polygon 0
3
0 0
2 0
1 1
2 
0 1
0 0