Zid magic
Limbajele de programare acceptate: Pascal, C și C++
Compilatoarele utilizate: Borland Pascal 7.0 și Borland C++ 3.1
Descrierea problemei
În urma conflictelor dintre elfi și orci, sistemul de apărare al elfilor a fost serios afectat.
Din acest motiv se dorește construirea unui zid
magic de apărare care să cuprindă în interiorul său toate locuințele
elfilor.
Deoarece mulți dintre elfii cu capacități
magice au fost uciși în luptă, se dorește ca lungimea totală a zidului
să fie minimă.
Ca urmare, zidul va avea forma unui poligon
convex care trebuie să conțină toate casele elfilor în vârfuri, pe
laturi sau în interior.
Date de intrare
Fișierul de intrare INPUT.TXT conține pe prima linie numărul n al locuințelor elfilor.
Fiecare dintre următoarele n
linii va conține câte două numere întregi, separate printr-un spațiu,
care reprezintă coordonatele uneia dintre locuințele elfilor.
Date de ieșire
Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie numărul k al vârfurilor poligonului care reprezintă zidul magic.
Fiecare dintre următoarele k linii va conține câte două numere, separate printr-un spațiu, care reprezintă coordonatele unuia dintre vârfurile poligonului.
Aceste linii trebuie să descrie vârfurile poligonului în sens trigonometric.
Restricții și precizări
numărul locuințelor elfilor este cuprins între 3 și 5000;
nu pot exista două sau mai multe locuințe ale elfilor la aceleași coordonate;
există posibilitatea ca trei sau mai multe locuințe să aibă coordonatele situate pe aceeași linie;
toate coordonatele sunt numere întregi cuprinse între 1 și 5000.
Exemplu
INPUT.TXT
8
10 10
10 20
15 15
20 10
20 20
12 18
18 12
14 11
OUTPUT.TXT
4
10 10
10 20
20 20
20 10
Timp de execuție: 2 secunde/test
|