Rezolvare completă PbInfo #1622 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ța

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 ≤ xi , yi ≤ 106;
  • 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ă 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.

Exemplul 1

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

Explicație

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.

Exemplul 2

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

Explicație

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

Exemplul 3

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ție

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.

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

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Elicoptere:

#include <fstream>
#include <math.h>
#include <iomanip>
using namespace std;
ifstream fin("elicoptere.in");
ofstream fout("elicoptere.out");
struct punct{
double x,y;
};
struct tri{
punct A,B,C;
};
tri T[1001];
int n,k,c[1001],v[1001],u,nrc,w;
double a[105][105];
int b[105][105];
long long perechi;

void cit(){
int i;
fin>>w;
fin>>n>>k;
for(i=1;i<=n;i++)
    fin>>T[i].A.x>>T[i].A.y>>T[i].B.x>>T[i].B.y>>T[i].C.x>>T[i].C.y;
fin.close();
}

double min(double x, double y){
if(x<y) return x;
return y;
}


double distLaturaOrizontala(punct M, punct P, punct Q){
double a,b,c;
punct N;
a=Q.y-P.y;
b=P.x-Q.x;
c=P.y*Q.x-P.x*Q.y;
if(P.y==M.y && M.y==Q.y){
    return min(fabs(P.x-M.x),fabs(Q.x-M.x));
}

if(P.y==Q.y)
    return 1000000;

N.y=M.y;
N.x=(-b*M.y-c)/a;
if((P.y<=M.y && M.y<=Q.y)||(Q.y<=M.y && M.y<=P.y))
    return sqrt((M.x-N.x)*(M.x-N.x)+(M.y-N.y)*(M.y-N.y));
return 1000000;
}

double distLaturaVerticala(punct M, punct P, punct Q){
double a,b,c;
punct N;
a=Q.y-P.y;
b=P.x-Q.x;
c=P.y*Q.x-P.x*Q.y;
if(P.x==M.x && M.x==Q.x)
    return min(fabs(P.y-M.y),fabs(Q.y-M.y));

if(P.x==Q.x)
    return 1000000;

N.x=M.x;
N.y=(-a*M.x-c)/b;
if((P.x<=M.x && M.x<=Q.x)||(Q.x<=M.x && M.x<=P.x))
    return sqrt((M.x-N.x)*(M.x-N.x)+(M.y-N.y)*(M.y-N.y));
return 1000000;
}


double distTriOrizontala(tri W, tri V){
double Min,d;
Min=1000000;
d=distLaturaOrizontala(W.A,V.A,V.B);
if(d<Min)
    Min=d;
d=distLaturaOrizontala(W.A,V.A,V.C);
if(d<Min)
    Min=d;
d=distLaturaOrizontala(W.A,V.B,V.C);
if(d<Min)
    Min=d;
d=distLaturaOrizontala(W.B,V.A,V.B);
if(d<Min)
    Min=d;
d=distLaturaOrizontala(W.B,V.A,V.C);
if(d<Min)
    Min=d;
d=distLaturaOrizontala(W.B,V.B,V.C);
if(d<Min)
    Min=d;
d=distLaturaOrizontala(W.C,V.A,V.B);
if(d<Min)
    Min=d;
d=distLaturaOrizontala(W.C,V.A,V.C);
if(d<Min)
    Min=d;
d=distLaturaOrizontala(W.C,V.B,V.C);
if(d<Min)
    Min=d;
return Min;
}

double distTriVerticala(tri W, tri V){
double Min,d;
Min=1000000;
d=distLaturaVerticala(W.A,V.A,V.B);
if(d<Min)
    Min=d;
d=distLaturaVerticala(W.A,V.A,V.C);
if(d<Min)
    Min=d;
d=distLaturaVerticala(W.A,V.B,V.C);
if(d<Min)
    Min=d;
d=distLaturaVerticala(W.B,V.A,V.B);
if(d<Min)
    Min=d;
d=distLaturaVerticala(W.B,V.A,V.C);
if(d<Min)
    Min=d;
d=distLaturaVerticala(W.B,V.B,V.C);
if(d<Min)
    Min=d;
d=distLaturaVerticala(W.C,V.A,V.B);
if(d<Min)
    Min=d;
d=distLaturaVerticala(W.C,V.A,V.C);
if(d<Min)
    Min=d;
d=distLaturaVerticala(W.C,V.B,V.C);
if(d<Min)
    Min=d;
return Min;
}

void matriceCost(){
int i,j;
double x1,x2,x;
for(i=1;i<=n;i++)
    for(j=i+1;j<=n;j++){
        x1=min(distTriOrizontala(T[i],T[j]),distTriVerticala(T[i],T[j]));
        x2=min(distTriOrizontala(T[j],T[i]),distTriVerticala(T[j],T[i]));
        x=min(x1,x2);
        if(x<=k)
        a[j][i]=a[i][j]=x;
            else
        a[j][i]=a[i][j]=1000000;
    }
}

void ad(int k){
int i;
u++;c[u]=k;v[k]=1;
for(i=1;i<=n;i++)
    if(v[i]==0 && a[k][i]<1000000 && a[k][i]!=0)
        ad(i);
}

long long comb2(int n){
long long c=n;
return c*(c-1)/2;
}

void componente(){
int i,j;
for(i=1;i<=n;i++)
    if(v[i]==0){
        u=0;nrc++;
        ad(i);
        b[nrc][0]=0;
        for(j=1;j<=u;j++){
            b[nrc][0]++;
            b[nrc][b[nrc][0]]=c[j];
        }
        perechi+=comb2(b[nrc][0]);
    }
}

double apm(int q){
int s[105],i,j,k;
double ct=0,d[105],Min;
s[b[q][1]]=1;
for(i=2;i<=b[q][0];i++){
    s[b[q][i]]=0;
    d[b[q][i]]=a[b[q][i]][b[q][1]];
}
for(k=1;k<b[q][0];k++){
    Min=1000000;
    for(i=1;i<=b[q][0];i++)
        if(s[b[q][i]]==0 && Min>d[b[q][i]]){
            Min=d[b[q][i]];
            j=i;
        }
    s[b[q][j]]=1;
    ct+=Min;
    for(i=1;i<=b[q][0];i++)
        if(s[b[q][i]]==0 && d[b[q][i]]>a[b[q][i]][b[q][j]])
            d[b[q][i]]=a[b[q][i]][b[q][j]];
}
return ct;
}

int main()
{
    double s=0,t;
    cit();
    matriceCost();
    componente();

    int i,j;
/*
    for(i=1;i<=nrc;i++){
        for(j=1;j<=b[i][0];j++)
            fout<<b[i][j]<<" ";
        fout<<'\n';
    }
*/
    for(i=1;i<=nrc;i++){
        t=apm(i);
        s+=t;
    }
     if(w==1)
         fout<<n-nrc<<'\n';
    if(w==2)
         fout<<perechi<<'\n';
    if(w==3)
         fout<<fixed<<setprecision(10)<<s<<'\n';
   fout.close();
   return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email.

Rezolvarea problemei #1622 Elicoptere

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1622 Elicoptere de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!