Noul maestru al dragonilor controlează un număr de N puncte de observație ale căror coordonate se cunosc. Nu există trei puncte de observație ale căror coordonate sunt puncte coliniare. Pentru a se proteja de următorul atac al megadragonilor, el decide să trimită câte un dragon la fiecare dintre punctele de observație aflate pe perimetrul teritoriului. Acest perimetru este dat de poligonul de perimetru minim care conține în interior sau în vârfuri toate punctele de observație.
Datorită faptului că maestrul dragonilor știe că, mai devreme sau mai târziu, acest perimetru va fi străpuns, el organizează apărarea în continuare astfel: ![]() ![]() ![]() ![]() Va trebui să determinați, pentru fiecare punct de observație în parte, numărul dragonilor care vor fi trimiși la punctul de observație respectiv.
Prima linie a fișierului de intrare DRAGONS.IN conține numărul N al punctelor de observație de pe teritoriul maestrului dragonilor. Fiecare dintre următoarele N linii va conține o pereche de numere reale reprezentând coordonatele unui punct de observație, separate prin câte un spațiu.
Fișierul de ieșire DRAGONS.OUT trebuie să conțină N linii; fiecare linie corespunde unui punct de observație. O astfel de linie va conține un singur număr care reprezintă numărul dragonilor trimiși la punctul de observație respectiv. Ordinea punctelor de observație din fișierul de ieșire trebuie să respecte ordinea acestora din fișierul de intrare.
![]() ![]() ![]()
DRAGONS.IN
16 8 2 2 4 17 4 6 5 8 7 11 9 15 10 12 18 5.1 16 4 20 15 18 7 15 6 14 11 13 12 13 13 14 DRAGONS.OUT 1 1 1 2 3 3 2 2 2 1 1 3 3 4 4 3 |