Concurs



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:
punctele de observație aflate pe perimetru (în vârfurile poligonului) sunt considerate a fi pierdute;
pentru punctele de observație rămase se determină un nou perimetru și la punctele de observație aflate pe noul perimetru sunt trimiși câte doi dragoni;
evident, și acest perimetru va fi străpuns, deci este organizat un al treilea nivel de apărare care va fi dat de perimetrul punctelor de observație rămase; la punctele de observație de pe acest perimetru vor fi trimiși câte trei dragoni;
procedeul va continua (numărul dragonilor crește cu 1 pentru fiecare nou perimetru) până în momentul în care nu va mai rămâne nici un punct de observație.
    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.

1 <= N <= 1000;
coordonatele punctelor de observație sunt numere reale cu cel mult trei zecimale exacte;
eventual, ultimul "perimetru" poate conține unul sau două puncte de observație.

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