Fişierul intrare/ieşire: | dr.in, dr.out | Sursă | Happy Coding 2008 |
Autor | Mugurel Ionut Andreica | Adăugată de | Mugurel-Ionut Andreica •mugurelionut |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Dr
Se dau N puncte in plan, incluse intr-un dreptunghi D=[0,Xmax]x[0,Ymax] (avand coltul stanga jos la (0,0) si cel dreapta-sus la (Xmax,Ymax)). Determinati aria maxima a unui dreptunghi avand laturile paralele cu axele de coordonate, care este inclus complet in dreptunghiul D si care nu contine nici unul din cele N puncte in interior (dar poate avea puncte pe laturi).
Date de intrare
Prima linie a fisierului de intrare dr.in contine numarul intreg T, reprezentand numarul de teste descrise in continuare. Prima linie a unui test contine 3 numere intregi, separate prin cate un spatiu: N, Xmax si Ymax. Urmatoarele N linii din cadrul testului contin cate 2 numere intregi X si Y, reprezentand coordonatele (X,Y) ale cate unui punct.
Date de iesire
In fisierul de iesire dr.out veti afisa pentru fiecare test, in ordinea in care apar testele in fisierul de intrare, aria maxima a unui dreptunghi complet inclus in dreptunghiul [0,Xmax]x[0,Ymax] si care nu contine nici unul din cele N puncte in interiorul sau (decat, eventual, pe laturi).
Restrictii
- 1 ≤ T ≤ 10
- 0 ≤ N ≤ 1000
- 1 ≤ Xmax, Ymax ≤ 10000
- Coordonatele fiecarui punct sunt numere intregi din dreptunghiul [0,Xmax]x[0,Ymax].
Exemplu
dr.in | dr.out |
---|---|
3 0 10 20 1 10000 10000 997 3456 4 999 88 10 40 990 40 500 80 500 8 | 200 90030000 70560 |