Fişierul intrare/ieşire:pomi.in, pomi.outSursăONIS 2014, Runda 2
AutorPaul DiacAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test1 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pomi

Ghita Ciobanul detine in apropierea stanii sale o livada cu M pomi. Aceasta este ingradita de un gard format din N tarusi intre care Ghita Ciobanul a legat sarma ghimpata, izoland astfel toti cei M pomi in interiorul unui poligon. Sfatuit de un prieten de pe Facebook, Ghita a construit gardul astfel incat poligonul format sa fie convex, iar pomii sunt strict in interiorul acestui poligon.

Alti doi ciobani de la stani invecinate i-au pus gand rau lui Ghita si intr-o noapte cand acesta vorbea la telefon i-au distrus gardul livezii, furand tarusii si sarma din care acesta era format. Ghita trebuie sa reconstruiasca gardul cat mai rapid, insa nu a mai gasit decat P tarusi si nici nu are timp sa sape noi gropi pentru acestia, astfel incat le va refolosi pe cele vechi. Deoarece P <= N, practic el trebuie sa selecteze acum doar P dintre cele N coordonate la care se aflau initial tarusii si sa construiasca gardul folosindu-se de acestea, pozitionand noii tarusi pe aceste coordonate. Interesul lui este sa aleaga pozitiile tarusilor astfel incat sa maximizeze numarul de copaci care se vor afla strict in interiorul noului poligon. Este posibil ca unul din copaci sa se afle acum pe granita poligonului, dar acesta nu trebuie luat in calcul deoarece nu este cu adevarat ingradit.

Date de intrare

Fişierul de intrare pomi.in contine pe prima linie numarul de teste T. In continuare, urmeaza descrierea fiecarui test astfel:
O prima linie cu numerele intregi N, M, P.
Urmatoarele N linii contin perechi de coordonate x, y reprezentand coordonatele varfurilor poligonului initial, specificate in ordinea acelor de ceasornic.
Urmatoarele M linii contin coordonatele pomilor care sunt in interiorul poligonului initial si sunt tot numere intregi.

Date de ieşire

În fişierul de ieşire pomi.out : pentru fiecare test afisati numarul maxim de pomi care pot fi ingraditi conform restrictiilor, pe cate o linie separata.

Restricţii

  • 3 ≤ N, M ≤ 100
  • 3 ≤ P ≤ N
  • Coordonatele sunt numere naturale ≤ 100000
  • Fisierul de intrare va contine maxim 5 teste

Exemplu

pomi.inpomi.out
1
6 17 3
6 13
13 10
13 4
8 2
3 4
1 9
2 8
2 9
3 6
3 9
5 5
5 11
6 4
7 9
7 11
8 6
9 4
9 8
10 9
11 5
11 10
12 7
12 9
8

Explicatie

Triunghiul cu varful in coordonatele (6, 13) (13, 10) (8, 2) contine 8 pomi in interior : (7, 9) (7, 11) (8, 6) (9, 4) (9, 8) (10, 9) (11, 10) (12, 9), iar 8 este numarul maxim de pomi care pot fi imprejmuiti de un triunghi cu varfurile in punctele initiale.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content