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.
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, 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.
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
Urmatoarele M linii contin coordonatele pomilor care sunt in interiorul poligonului initial si sunt tot numere intregi.
Fisierul se termina cu o linite suplimentara pe care se afla numarul 0.
h2. Date de ieşire
În fişierul de ieşire $pomi.out$ ...
În fişierul de ieşire $pomi.out$
Pentru test afisati numarul maxim de pomi care pot fi ingraditi conform restrictiilor, pe o linie separata.
h2. Restricţii
* $... ≤ ... ≤ ...$
* N, M ≤ 100
* P ≤ N
* Coordonatele sunt numere naturale ≤ 100000
h2. Exemplu
table(example). |_. pomi.in |_. pomi.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 17 3
6 13
13 10
13 4
8 2
3 4
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
0
| ?
|
h3. Explicaţie
h3. Triunghiu cu varful in coordonatele x1, y1, x2, y2, x3, y3 contine R pomi in interior.
...