Državno natjecanje 2016. godine za 1. i 2. razred Srednje Škole - 2. zadatak - 1. dan

Stado koza mirno pase na pašnjaku te ih je potrebno ograditi kako ih ne bi dohvatile divlje zvijeri. Pašnjak je smješten u standardni koordinatni sustav u kojem x koordinata raste nadesno, a y koordinata prema gore. Polje je kvadrat duljine stranice jedan, sa stranicama paralelnim s koordinatnim osima, takav da su koordinate njegovog donjeg lijevog vrha A = (xA, yA) oba nenegativni cijeli brojevi.

Tor je skup od jednog ili više polja za kojeg vrijedi:

• Sva polja koja su dio tora su međusobno povezana – moguće je od svakog polja doći do svakog drugog polja tako da se u svakom koraku pomaknemo na susjedno polje gore, dolje, lijevo ili desno.

• Tor nema rupa – moguće je od svakog polja koje nije dio tora dođi do svakog drugog polja koje nije dio tora tako da se u svakom koraku pomaknemo na susjedno polje gore, dolje, lijevo ili desno.

  

Ograda tora je poligon koji opisuje njegov rub. Zadan je skup polja koji čini tor, odredite njegovu ogradu.

Poligon ispišite kao niz koordinata vrhova T1, T2, . . . , Tm redom kojim dolaze u smjeru suprotnom od kazaljke na satu počevši od vrha koji je najlijeviji te najdonji među svim najlijevijim vrhovima poligona. Također, dva susjedna brida ne smiju biti paralelna, pa brid T1T2 mora biti horizontalan, brid T2T3 vertikalan i tako naizmjence dalje do brida TmT1 koji mora biti vertikalan. Primijetite da ovi uvjeti na jedinstven način određuju ispis poligona.

ULAZNI PODACI

U prvom redu nalazi se prirodni broj n (n ≤ 1000) broj polja u toru. U k-tom od sljedećih n redova nalaze se cijeli brojevi xk i yk (0 ≤ xk, yk ≤ 1000) – koordinate donjeg lijevog vrha k-tog polja tora. Možete pretpostaviti da polja čine ispravan tor prema definiciji iz teksta zadatka.

IZLAZNI PODACI

U prvi red ispišite prirodni broj m – broj vrhova ograde. U k-tom od sljedećih m redova ispišite cijele brojeve xk i yk – koordinate k-tog vrha ograde Tk.

PRIMJERI TEST PODATAKA

ulaz

4
0 0
1 0
0 1
1 1

izlaz

4
0 0
2 0
2 2
0 2

ulaz

11
0 0
1 0
1 1
2 1
2 2
3 3
4 2
1 2
3 2
1 3
0 3

izlaz

18
0 0
2 0
2 1
3 1
3 2
5 2
5 3
4 3
4 4
3 4
3 3
2 3
2 4
0 4
0 3
1 3
1 1
0 1