Szklana pułapka

Limit pamięci: 64 MB

W pałacu króla Bajtazara straszy duch. Złośliwi twierdzą, że jest to duch niedawno zmarłej (w podejrzanych okolicznościach) małżonki Bajtazara, gdyż tak jak ona, bardzo lubi przeglądać się w lustrach. Nie dziwi więc, że Bajtazar chętnie pozbyłby się ducha.

Bajtazar postanowił w jednej z komnat pałacu przygotować specjalną szklaną pułapkę. Jest to zamknięta, dobrze oświetlona sala, której wszystkie ściany wewnętrzne pokryte są lustrami. Ponadto w każdym rogu sali może być umieszczony laser albo czujnik promieni laserowych. Gdy tylko duch przetnie wiązkę jednego z laserów, podniesie się alarm, a sprowadzeni przez Bajtazara pogromcy duchów rozprawią się z nim.

Sala, w której powstaje szklana pułapka, ma kształt wielokąta o sąsiednich bokach prostopadłych do siebie. Ponadto długość każdej ściany (wyrażona w metrach) jest całkowita. Jeżeli w danym rogu sali ma być umieszczony laser, to jego promień musi być skierowany wzdłuż dwusiecznej kąta, jaki tworzą stykające się w tym rogu ściany (i zarazem równolegle do podłogi). Oczywiście, jeżeli promień lasera napotka na swojej drodze lustro, to odbija się od niego pod takim samym kątem, pod jakim pada, czyli 45 stopni. Promień wpadający wzdłuż dwusiecznej kąta w róg sali z czujnikiem zostaje całkowicie pochłonięty przez czujnik. Promień wpadający wzdłuż dwusiecznej kąta w róg sali bez czujnika (za to być może z innym laserem) jest odbijany o 180 stopni. W innych przypadkach promień kontynuuje wędrówkę po sali, nie zmieniając kierunku.

W sali należy rozmieścić maksymalnie dużo laserów i odpowiadających im czujników, w taki sposób, żeby promień każdego lasera wpadał do jakiegoś czujnika, promienie różnych laserów wpadały do różnych czujników oraz żeby do każdego czujnika wpadał promień pewnego lasera. Przy tym w każdym rogu można zainstalować tylko albo laser, albo czujnik, ale nie jedno i drugie.

Przykład szklanej pułapki z promieniem lasera biegnącym z rogu 1 do rogu 7.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis kształtu szklanej pułapki,
• wyznaczy sposób rozmieszczenia maksymalnej liczby laserów i czujników spełniający warunki zadania,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba całkowita (). Jest to liczba ścian szklanej pułapki. W każdym z następnych wierszy znajdują się po dwie liczby całkowite: i oznaczające współrzędne rogu nr (, ), przedzielone pojedynczą spacją. Każde dwa kolejne rogi połączone są ścianą równoległą do jednej z osi współrzędnych. Żadne dwie ściany nie przecinają się i nie mają punktów wspólnych, z wyjątkiem dwóch kolejnych ścian, które stykają się we wspólnym rogu. Kolejne rogi pomieszczenia podane są w kolejności zgodnej z ruchem wskazówek zegara (tzn. przy obchodzeniu pomieszczenia wzdłuż ścian wnętrze znajduje się zawsze po prawej stronie). Łączna długość wszystkich ścian nie przekracza .

Wyjście

Twój program powinien w pierwszym wierszu standardowego wyjścia wypisać jedną liczbę całkowitą , oznaczającą maksymalną liczbę par laser-czujnik, jakie można umieścić w szklanej pułapce. W każdym z następnych wierszy powinna znaleźć się para liczb i oddzielonych pojedynczą spacją, gdzie oznacza numer rogu, w którym powinien znaleźć się laser, zaś - numer rogu, w którym powinien znaleźć się odpowiadający mu czujnik, przy czym . W przypadku, gdy istnieje wiele rozwiązań, należy podać dowolne z nich.

Przykład

Dla danych wejściowych:

10
1 1
3 1
3 -2
-3 -2
-3 0
-1 0
-1 -1
2 -1
2 0
1 0

poprawną odpowiedzią jest:

5
10 5
1 7
2 9
3 8
4 6

Przykładowe rozmieszczenie systemu laserów i czujników w szklanej pułapce przedstawia rysunek.

Autor zadania: Marian M. Kędzierski.