Rezumat problemă

smin

#750

Ana are un joc nou. Pe o tablă pătrată este trasat un grid format din celule pătratice de dimensiune 1. În oricare dintre colţurile oricărei celule, Ana poate înfige câte un beţişor perpendicular pe tablă. După ce a plasat n beţişoare, Ana ia dintr-o cutie (cu un număr suficient de mare de corzi elastice circulare) câte o coardă cu care înconjoară trei sau mai multe beţişoare. Fiecare coardă este bine întinsă şi formează pe tablă un contur poligonal.
În figura alăturată este folosită o coardă ce formează un contur poligonal cu 4 laturi cu care sunt înconjurate 5 dintre cele 8 beţişoare de pe tablă.

Jocul se încheie când au fost plasate atâtea coarde încât toate beţişoarele de pe tablă să se afle pe marginea sau în interiorul a cel puţin unul dintre contururile poligonale formate. Scopul jocului este ca amplasarea corzilor să fie făcută convenabil astfel încât totalul ariilor contururilor poligonale formate să fie minim.

Cunoscând coordonatele celor n beţişoare (x[1], y[1]), (x[2], y[2]), …, (x[n], y[n]) măsurate faţă de unul dintre colţurile gridului, Ana doreşte să găsească suma minimă a ariilor poligonale obţinute prin amplasarea convenabilă a coardelor, astfel încât fiecare beţişor să se găsească în interiorul sau pe conturul a cel puţin un astfel de poligon.

Lot Juniori, Cluj Napoca, 2009

Fișiere Candale Silviu (silviu) Suzana Galatan concurs

Clasa 9 Tablouri unidimensionale (vectori) Probleme diverse

Rezolvă

Detalii

Problema	smin	Operații I/O	smin.in/smin.out
Limita timp	2.5 secunde	Limita memorie	Total: 16 MB / Stivă 16 MB
Id soluție	#63991063	Utilizator	bivolu emanuel (bivolaru)
Fișier	smin.cpp	Dimensiune	930 B
Data încărcării	02 Aprilie 2026, 13:21	Scor/rezultat	Eroare de compilare

Evaluare

Mesaj compilare

smin.cpp:2:13: error: expected type-specifier before 'pair'
 using pii = pair<int, int>;

             ^
smin.cpp:7:1: error: 'pii' does not name a type
 pii v[21];

 ^
smin.cpp:10:13: error: 'pii' was not declared in this scope
 double arie(pii p1, pii p2, pii p3) {

             ^
smin.cpp:10:21: error: 'pii' was not declared in this scope
 double arie(pii p1, pii p2, pii p3) {

                     ^
smin.cpp:10:29: error: 'pii' was not declared in this scope
 double arie(pii p1, pii p2, pii p3) {

                             ^
smin.cpp:10:35: error: expression list treated as compound expression in initializer [-fpermissive]
 double arie(pii p1, pii p2, pii p3) {

                                   ^
smin.cpp:10:37: error: expected ',' or ';' before '{' token
 double arie(pii p1, pii p2, pii p3) {

                                     ^
smin.cpp: In function 'int main()':
smin.cpp:17:36: error: 'v' was not declared in this scope
   for (int i = 0; i < n; i++) f >> v[i].first >> v[i].second;

                                    ^
smin.cpp:18:30: warning: overflow in implicit constant conversion [-Woverflow]
   memset(dp, sizeof(dp), 1e18);

                              ^
smin.cpp:25:46: error: 'v' was not declared in this scope
           dp[z] = min(dp[z], dp[mask] + arie(v[p1], v[p2], v[p3]));

                                              ^
smin.cpp:25:65: error: 'arie' cannot be used as a function
           dp[z] = min(dp[z], dp[mask] + arie(v[p1], v[p2], v[p3]));

                                                                 ^

Cum funcționează evaluarea?