elicoptere

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

Cerinţă

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

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 și 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 minim de elicoptere, ce vor fi 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 minimă a lungimii rutelor parcurse de elicoptere.

Restricţii şi precizări

• 1 ≤ n ≤ 100;
• 1 ≤ k ≤ 1000;
• coordonatele vârfurilor insulelor sunt numere naturale $0 ≤ x_i , y_i ≤ 10^6$;
• orice două insule nu au puncte comune;
• la cerința 2, dacă se poate ajunge din insula A în insula B atunci evident că se poate ajunge și din B în A, deci 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 a calcula şi afișa un număr real x cu o precizie cât mai mare vă recomandăm folosirea tipului double
• Pentru rezolvarea corectă a cerinței 1 se acordă 40% din punctaj;
• Pentru rezolvarea corectă a cerinței 2 se acordă 20% din punctaj;
• Pentru rezolvarea corectă a cerinței 3 se acordă 40% din punctaj.

Exemple

elicoptere.in

1
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

elicoptere.out

3

elicoptere.in

2
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

elicoptere.out

4

elicoptere.in

3
6 11
100 20 100 30 105 30
20 20 30 30 20 30
200 20 200 30 205 30
100 40 100 50 105 40
10 40 5 40 10 50
10 20 5 30 10 30

elicoptere.out

30

Explicații

Pentru primul test:
Datele corespund figurilor anterioare :
v = 1, deci se rezolvă NUMAI prima cerință.
Perechile de insule cu transport direct cu elicoptere: (1,4) (2,6), (6,5) și obținem astfel 3 elicoptere.

Pentru al doilea test:
Datele corespund figurilor anterioare :
v = 2, deci se rezolvă NUMAI a doua cerință.
Perechile de insule cu transport direct cu elicoptere: (1,4) (2,6), (6,5) și obținem astfel 3 elicoptere.
Insula 3 rămâne izolată, astfel avem două grupuri de insule. Primul grup conţine insulele 1 şi 4, iar al doilea insulele 2, 5, 6. Din primul grup se numara perechea (1,4), iar din al doilea grup se numara perechile de insule (2,5), (2,6) si (5,6). In total 4 perechi de insule intre care se poate deplasa cu elicopterul direct sau cu escala (indirect).

Pentru ultimul test:
Datele corespund figurilor anterioare :
v = 3, deci se rezolvă NUMAI a treia cerință.
Perechile de insule cu transport direct cu elicoptere: (1,4) (2,6), (6,5) și obținem astfel 3 elicoptere.
Insula 3 rămâne izolată, astfel avem două grupuri de insule. Primul grup conţine insulele 1 şi 4, iar al doilea insulele 2, 5, 6.
Elicopeterele asigură transportul direct între insulele:
1 şi 4 cu distanţa verticală egală cu 10;
2 şi 6 cu distanţa orizontală egală cu 10;
5 şi 6 cu distanţa verticală egală cu 10;
În total liniile de transport au distanţa 30.