Fişierul intrare/ieşire:	elicoptere.in, elicoptere.out	Sursă	OJI 2016, clasele 11-12
Autor	Doru Popescu Anastasiu	Adăugată de	Vlad Rochian •vladrochian
Timp execuţie pe test	0.1 sec	Limită de memorie	8192 kbytes
Scorul tău	N/A	Dificultate	2/5

Vezi solutiile trimise | Statistici

Elicoptere

Arhipeleagul 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 în linie dreaptă, pe distanţa minimă obţinută pe orizontală sau pe verticală. Astfel, ruta va putea fi reprezentată în sistemul cartezian ca un segment orizontal sau vertical, cu capetele aparţinând interiorului sau conturului celor două insule pe care le uneşte. În plus, datorită capacităţii limitate a rezervorului, lungimea unei rute nu poate depăşi o valoare K. Deplasarea persoanelor între două insule se poate realiza direct, cu un singur elicopter, sau indirect, cu escale (utilizând două sau mai multe elicoptere). Elicopterele parcurg rutele în ambele sensuri.

Investiţia trebuie să îndeplinească următoarele condiţii:

• Numărul de perechi de insule între care se va putea realiza direct sau indirect transportul să fie maxim.
• Numărul de elicoptere cumpărate pentru a realiza acest lucru să fie minim.
• Suma lungimii tuturor rutelor să fie minimă.

Cerinţă

Să se scrie un program care, cunoscând N, K şi coordonatele vârfurilor insulelor, determină, pentru investiţia descrisă mai sus:

1. Numărul de elicoptere ce vor fi cumpărate.
2. Numărul perechilor neordonate de insule între care se va putea realiza transportul direct sau indirect cu elicoptere.
3. Suma lungimilor tuturor rutelor parcurse de elicopterele cumpărate.

Date de intrare

Fişierul de intrare elicoptere.in conţine pe prima linie o valoare v ce poate fi 1, 2 sau 3, în funcţie de cerinţa ce va fi rezolvată, pe linia a doua numerele naturale N şi K separate printr-un spaţiu, cu semnificaţia de mai sus, iar pe următoarele N linii se află câte şase numere naturale x1, y1, x2, y2, x3, y3 separate prin spaţiu reprezentând coordonatele celor trei vârfuri ale insulelor în formatul (abscisă, ordonată).

Date de ieşire

Dacă valoarea lui v este 1 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie numai numărul de elicoptere cumpărate de administraţie.

Dacă valoarea lui v este 2 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie numai numărul maxim de perechi de insule între care se poate realiza transportul prin elicoptere.

Dacă valoarea lui v este 3 atunci fişierul de ieşire elicoptere.out va conţine pe prima linie suma lungimilor rutelor parcurse de elicoptere.

Restricţii

• 1 ≤ N ≤ 100
• 1 ≤ K ≤ 1 000
• Coordonatele vârfurilor insulelor sunt numere naturale din intervalul [0, 10⁶].
• Oricare două insule nu au puncte comune.
• Dacă se poate ajunge din insula A în insula B atunci evident că se poate ajunge şi din B în A, deci, la cerinţa 2, perechea formată din A şi B se numără o singură dată.
• Distanţa dintre două insule poate fi şi număr real.
• La cerinţa 3, rezultatul se cere cu o aproximaţie de 0.001, adică rezultatul notat cu R se consideră corect dacă faţă de rezultatul comisiei C îndeplineşte condiţia |R - C| < 0.001.
• Pentru rezolvarea corectă a cerinţei 1 se acordă 20% din punctaj.
• Pentru rezolvarea corectă a cerinţei 2 se acordă 40% din punctaj.
• Pentru rezolvarea corectă a cerinţei 3 se acordă 40% din punctaj.

Exemplu

Explicaţie

Vor fi cumpărate 3 elicoptere ce vor lega direct perechile de insule (1, 4), (2, 6) şi (5, 6). De asemenea între insulele (2, 5) se poate realiza transport indirect cu escală în 6, deci la cerinţa 2 vom avea în total 4 perechi. Insula 3 rămâne izolată.

Pentru toate cele 3 perechi de insule legate direct, distanţa minimă dintre acestea este egală cu 10, deci suma lungimilor rutelor va fi 30.

Cum se trimit solutii?