poligon

Разглеждаме изпъкнал многоъгълник с n върха. Той е зададен с  координатите на върховете си по посока на обхождането им по часовниковата стрелка.  Точката S от равнината на многоъгълника наричаме център на симетрия, ако образът при централна симетрия стрямо S на всяка точка от многоъгълника е също точка от многоъгълника.

Задача

Да се провери дали даден многоъгълник има център на симетрия. Ако такъв център съществува, да се раздели многоъгълникът на успоредници.

Вход

Входният файл poligon.in съдържа в първия си ред едно цяло положително число k, което задава броя на тестовете. На следващите редове са дадени k групи от данни, по една група за всеки тест. Всяка група съдържа един ред със стойността на n, следван от n реда с координатите на върховете на многоъгълника в следния формат:
n
x1 y1
x2 y2

xn yn

Изход

Изходният файл poligon.out трябва да съдържа отговорите на тестовете от входния файл. За всеки тест трябва да бъде изведено на отделен ред едно цяло положително число h, показващо броя на успоредниците, на които съответният многоъгълник се разлага, следвано от h реда, съдържащи координатите на върховете на успоредниците в следния формат:
h
px11 py11 px21 py21 px31 py31 px41 py41
px12 py12 px22 py22 px32 py32 px42 py42

px1h py1h px2h py2h px3h py3h px4h py4h
Всеки успоредник е определен от координатите (абсциса и ордината) на върховете си по посока на обхождане по часовниковата стрелка.

Ограничения и пояснения

Пример

poligon.in

poligon.out

2
4
10 20
40 30
40 10
20 10
8
20 30
30 30
40 20
40 10
30 0
20 0
10 10
10 20

0
6
20 0 10 10 20 10 30 0
10 10 10 20 20 20 20 10
10 20 20 30 30 30 20 20
20 10 20 20 30 10 30 0
20 20 30 30 40 20 30 10
40 20 40 10 30 0 30 10

Ограничение за време: 0.1 сек. за тест

prof. Doru Popescu Anastasiu
"Radu Greceanu" National College Slatina
Contact:dopopan@yahoo.com

Превод на български: Емил Келеведжиев