------------------------------------------------------
| PROBLEMA 40: STRATURI |
| DEADLINE: Miercuri, 9 FEBRUARIE 2000 |
| DOMENIU: xoy |
| TIMP DE IMPLEMENTARE: 1h 30' |
| PUNCTAJ: 60 dex |
| TIMP DE EXECUTIE: 1sec/test (Pentium II) |
------------------------------------------------------
Fie Q o multime formata din n puncte din plan.
Spunem ca punctul (x, y) DOMINA punctul (x0, y0) daca si numai daca
( x > x0 ) SI ( y > y0 ).
Un punct din Q care nu este dominat de nici un alt punct din Q se
numeste PUNCT MAXIMAL.
Punctele maximale vor fi organizate in straturi dupa cum urmeaza:
· Primul strat maximal, L1, este multimea de puncte maximale din Q;
· Pentru i > 1, stratul maximal Li este multimea punctelor maximale
din multimea Q - { L1 + ... + L(i-1) }.
Dandu-se la intrare numarul n de puncte (1 <= n <= 5000) si
coordonatele lor intregi, se cere sa se afle toate straturile
maximale.
Observatie: pentru orice i si j din {1..n}, se garanteaza ca
xi <> xj si yi <> yj,
-30 000 <= xi , yi <= 30 000
Date de intrare - in fisierul LAYERS.IN :
n pe prima linie n, numarul de puncte
x1 y1 pe urmatoarele n linii coordonatele intregi ale celor n puncte
.....
xn yn
Date de iesire - in fisierul LAYERS.OUT:
Pe prima linie se va afisa numarul s de straturi gasite, si pentru
fiecare strat Li de la 1 la n ( in aceasta ordine! ) se vor afisa:
Pe o linie Ni = numarul de puncte din acel strat , urmat de Ni linii
continand coordonatele pe x si pe y ale fiecarui punct din Li
separate printr-un spatiu.
In fisierul layers.out :
s pe prima linie n, numarul de straturi gasite
n1 numarul de puncte din primul strat
X11 Y11 coordonatele pe x si pe y ale fiecarui punct din L1.
.....
X1n1 Y1n1
n2 numarul de puncte din al doilea strat
X21 Y21 coordonatele pe x si pe y ale fiecarui punct din L2.
.....
X2n2 Y2n2
.............................
ns numarul de puncte din ultimul strat
Xs1 Ys1 coordonatele pe x si pe y ale fiecarui punct din Ls.
.....
Xsns Ysns
Exemplu:
Layers.in
2
1 3
2 7
Layers.out
2
1
2 7
1
1 3
</tt>
|
|
