Rezumat problemă

Elicoptere

#1622

Arhipelagul Zopopan este format din n insule de formă triunghiulară numerotate de la 1 la n. Fiecare insulă este localizată prin coordonatele carteziene ale vârfurilor.

Administrația dorește să cumpere elicoptere pentru a realiza transportul între insule. Un elicopter va putea să asigure o rută între două insule pe distanța minimă obținută pe orizontală sau verticală (paralel cu axele de coordonate). În plus, datorită capacității rezervorului o astfel de rută nu poate să depășească o valoare k – număr natural. Elicopterele parcurg rutele în ambele sensuri.
Investiția trebuie să îndeplinească următoarele condiții:

1. Numărul de elicoptere cumpărate să fie minim.
2. Numărul de perechi de insule între care se poate realiza transportul, folosind unul sau mai multe elicoptere să fie maxim.
3. Suma lungimii tuturor rutelor să fie minimă.

Să se scrie un program care pentru n, k şi coordonatele vârfurilor insulelor cunoscute, determină:

1. numărul minim de elicoptere ce vor fi cumpărate de administraţie;
2. numărul perechilor neordonate de insule între care se poate realiza transportul prin elicoptere direct sau indirect;
3. suma distantelor parcurse de toate elicopterele cumpărate (distanța parcursă de un elicopter se consideră distanța dintre insulele între care acesta asigură transportul).

OJI 2016, Clasele XI-XII

Fișiere Candale Silviu (silviu) Doru Popescu Anastasiu concurs

Clasa 11 Teoria Grafurilor Parcurgerea grafurilor neorientate Algoritmul lui Kruskal Geometrie

Rezolvă

Detalii

Problema	Elicoptere	Operații I/O	elicoptere.in/elicoptere.out
Limita timp	0.2 secunde	Limita memorie	Total: 4 MB / Stivă 4 MB
Id soluție	#56906184	Utilizator	Stoleriu Radu (RaduStoleriu)
Fișier	elicoptere.cpp	Dimensiune	2.68 KB
Data încărcării	10 Martie 2025, 15:29	Scor / rezultat	Eroare de compilare

Evaluare

Mesaj compilare

elicoptere.cpp: In function 'double Dist(triangle, triangle)':
elicoptere.cpp:84:11: warning: unused variable 'j' [-Wunused-variable]
     int i,j;

           ^
elicoptere.cpp: In function 'double perp(point, point, point)':
elicoptere.cpp:119:23: error: call of overloaded 'abs(double)' is ambiguous
         dver=abs(Y-A.y);

                       ^
elicoptere.cpp:119:23: note: candidates are:
In file included from /usr/include/c++/4.8/cstdlib:72:0,
                 from /usr/include/c++/4.8/ext/string_conversions.h:41,
                 from /usr/include/c++/4.8/bits/basic_string.h:2815,
                 from /usr/include/c++/4.8/string:52,
                 from /usr/include/c++/4.8/bits/locale_classes.h:40,
                 from /usr/include/c++/4.8/bits/ios_base.h:41,
                 from /usr/include/c++/4.8/ios:42,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/fstream:38,
                 from elicoptere.cpp:1:
/usr/include/stdlib.h:775:12: note: int abs(int)
 extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
            ^
In file included from /usr/include/c++/4.8/ext/string_conversions.h:41:0,
                 from /usr/include/c++/4.8/bits/basic_string.h:2815,
                 from /usr/include/c++/4.8/string:52,
                 from /usr/include/c++/4.8/bits/locale_classes.h:40,
                 from /usr/include/c++/4.8/bits/ios_base.h:41,
                 from /usr/include/c++/4.8/ios:42,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/fstream:38,
                 from elicoptere.cpp:1:
/usr/include/c++/4.8/cstdlib:174:3: note: long long int std::abs(long long int)
   abs(long long __x) { return __builtin_llabs (__x); }
   ^
/usr/include/c++/4.8/cstdlib:166:3: note: long int std::abs(long int)
   abs(long __i) { return __builtin_labs(__i); }
   ^
elicoptere.cpp:125:23: error: call of overloaded 'abs(double)' is ambiguous
         dorz=abs(X-A.x);

                       ^
elicoptere.cpp:125:23: note: candidates are:
In file included from /usr/include/c++/4.8/cstdlib:72:0,
                 from /usr/include/c++/4.8/ext/string_conversions.h:41,
                 from /usr/include/c++/4.8/bits/basic_string.h:2815,
                 from /usr/include/c++/4.8/string:52,
                 from /usr/include/c++/4.8/bits/locale_classes.h:40,
                 from /usr/include/c++/4.8/bits/ios_base.h:41,
                 from /usr/include/c++/4.8/ios:42,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/fstream:38,
                 from elicoptere.cpp:1:
/usr/include/stdlib.h:775:12: note: int abs(int)
 extern int abs (int __x) __THROW __attribute__ ((__const__)) __wur;
            ^
In file included from /usr/include/c++/4.8/ext/string_conversions.h:41:0,
                 from /usr/include/c++/4.8/bits/basic_string.h:2815,
                 from /usr/include/c++/4.8/string:52,
                 from /usr/include/c++/4.8/bits/locale_classes.h:40,
                 from /usr/include/c++/4.8/bits/ios_base.h:41,
                 from /usr/include/c++/4.8/ios:42,
                 from /usr/include/c++/4.8/istream:38,
                 from /usr/include/c++/4.8/fstream:38,
                 from elicoptere.cpp:1:
/usr/include/c++/4.8/cstdlib:174:3: note: long long int std::abs(long long int)
   abs(long long __x) { return __builtin_llabs (__x); }
   ^
/usr/include/c++/4.8/cstdlib:166:3: note: long int std::abs(long int)
   abs(long __i) { return __builtin_labs(__i); }
   ^
elicoptere.cpp: In function 'void dfs(int)':
elicoptere.cpp:132:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=0;i<G[nod].size();i++)

                           ^

Cum funcționează evaluarea?