== include(page="template/taskheader" task_id="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 tot cei M pomi in interiorul unui poligon. Stafuit astfel de un prieten de pe Facebook, Ghita a construit gardul astfel incat poligonul format este convex, iar pomii sunt strict in interiorul acestui poligon.
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, el trebuie sa selecteze acum doar P dintre cele N coordonate la care se aflau tarusii si sa construiasca gardul folosindu-se de acestia. Interesul lui este sa aleaga 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 pazit de gard.
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.
h2. Date de intrare
Fişierul de intrare $pomi.in$ contine mai multe teste, fiecare descris in felul urmator:
Pe prima linie se afla numerele intregi N, M, P.
Urmatoarele N linii contin perechi de coordonate intregi x y reprezentand coordonatele varfurilor poligonului initial care este convex iar varfurile sunt in ordinea acelor de ceasornic.
Urmatoarele M linii contin
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.
h2. Date de ieşire
În fişierul de ieşire $pomi.out$ ...
Î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.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $3 ≤ N, M ≤ 100$
* $3 ≤ P ≤ N$
* Coordonatele sunt numere naturale ≤ $100000$
* Fisierul de intrare va contine maxim $5$ teste
h2. Exemplu
table(example). |_. pomi.in |_. pomi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 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
|
h3. Explicaţie
h2. 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.
...
== include(page="template/taskfooter" task_id="pomi") ==
