Fişierul intrare/ieşire:pisica.in, pisica.outSursăAlgoritmiada 2019 Runda Maraton
AutorAlexandru PetrescuAdăugată deheracleRadu Muntean heracle
Timp execuţie pe test0.4 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Pisica

O pisica intr-o cusca.

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.inpisica.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?