Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | pisica.in, pisica.out | Sursă | Algoritmiada 2019 Runda Maraton |
| Autor | Alexandru Petrescu | Adăugată de |  Radu Muntean •heracle |
| Timp execuţie pe test | 0.4 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Pisica
Intro
Se da un poligon convex Pisica si un poligon convex Cusca. In varfurile poligonului Cusca se afla cate o bara de fier fixa si inalta. Cum sunt multe bare de fier, Pisica se simte mult prea constransa. Pana la urma, e o Pisica care traieste in secolul 21 si tine la libertatea ei. Asa ca Marcel, filantrop care intelege mecanismele timpului sau, s-a hotarat sa ii dea senzatia ca e libera, fara ca acest fapt sa fie si real.
Cerinta
Sa se scoata un numar maxim de bare din Cusca in asa fel incat Pisica sa nu poata evada, oricat s-ar roti si s-ar translata succesiv, stiind ca ea nu are voie sa atinga barele de fier ramase.
Date de intrare
Fişierul de intrare pisica.in contine pe prima linie numarul M de puncte care formeaza poligonul Pisica. Pe urmatoarele M linii se afla cate doua numere reale cu valori intre -400000 si 400000, cu pana la 4 zecimale, reprezentand, in ordine trigonometrica, varfurile poligonului Pisica. In acelasi format urmeaza, pe urmatoarele N + 1 linii, descrierea poligonului Cusca, care are N varfuri.
Date de ieşire
În fişierul de ieşire pisica.out se afla numarul de bare ramase in Cusca dupa ce au fost scoase cat mai multe, fara ca Pisica sa poata evada Cusca.
Restricţii si precizari
- 4 ≤ M ≤ 100.000
- 24 ≤ N ≤ 100.000
- Varfurile fiecarui poligon sunt puncte distincte
- Se garanteaza ca pisica nu poate iesi daca se pastreaza toate barele
- Se garanteaza ca daca Pisica s-ar ingrasa putin, sau ar slabi un pic, raspunsul ar ramane acelasi (testele sunt facute in asa fel incat sa nu existe probleme legate de precizia numerelor reale).
- Se garanteaza ca in situatia in care se pastreaza toate barele, pisica se poate roti/translata succesiv astfel incat sa atinga orice bara cu orice varf al ei.
- Pentru 60 de puncte, se garanteaza ca N ≤ 1.000 - feedback testul 10
- Meow!!!
- Restul testelor de feedback fac parte din testele cele mai mari
Exemplu
| pisica.in | pisica.out |
|---|---|
| 4 1.5 1.5 2.5 1.5 2.5 2.5 1.5 2.5 24 0 0 0.667 0 1.333 0 2 0 2.667 0 3.333 0 4 0 4 0.667 4 1.333 4 2 4 2.667 4 3.333 4 4 3.333 4 2.667 4 2 4 1.333 4 0.667 4 0 4 0 3.333 0 2.667 0 2 0 1.333 0 0.667 | 20 |
Explicaţie
Pisica e un patrat de latura 1 iar Cusca e un patrat de latura 4 in jurul ei, cu bare din ~2/3 in ~2/3. Putem scoate barele din colturile patratelor, dar alte bare nu putem scoate, pentru ca altfel pisicii i-ar fi prea usor sa scape.
