Cod sursa(job #2069192)

Utilizator Andreir52Andrei Rizescu Andreir52 Data 18 noiembrie 2017 12:21:38
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.55 kb
#include <iostream>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <vector>
#include <iomanip>
using namespace std;

struct punct
{
    int x,y;
}X, dreapta;
vector <punct> v,y;
int n,i,j;
double s=1000000000,smin1=1000000000,smin2=1000000000, smin=1000000000, s1=1000000000, s2=1000000000, s3=1000000000;

    ifstream f("date.in");
  ofstream g("date.out");
double Euclid (punct A , punct B)
{
      return (sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)));
}

bool comparare (punct A, punct B)
{
    return ((A.x<B.x) || (A.x==B.x) && (A.y<B.y));
}
bool comp (punct A, punct B)
{
    return (A.y<B.y);
}

void SolutieS(int st, int dr)                      //apelul recursiv pt partea stanga
{
 if((st+dr)>3){ dr=(st+dr)/2;
                if((dr-st+1)==2) s=Euclid(v[st],v[dr]);
                else { s1=Euclid(v[st],v[dr]);
                    s2=Euclid(v[st],v[st+1]);
                    s3=Euclid(v[st+1],v[dr]);
                    }
                    if(smin>s) smin=s;
                    if(smin>s1) smin=s1;
                    if(smin>s2) smin=s2;
                    if(smin>s3) smin=s3;

                SolutieS(st,dr);
                for(i=dr; i>=st; i--)
                    if(abs(v[st].x-v[i].x)<=smin) y.push_back(v[i]);


 }


}

void SolutieD(int st, int dr)                     //apelul recursiv pt partea dreapta
{
 if((dr-st+1)>3){ st=(st+dr)/2 + 1;
                   if((dr-st+1)==2) s=Euclid(v[st],v[dr]);
                   else { s1=Euclid(v[st],v[dr]);
                    s2=Euclid(v[st],v[st+1]);
                    s3=Euclid(v[st+1],v[dr]);
                    }
                    if(smin>s) smin=s;
                    if(smin>s1) smin=s1;
                    if(smin>s2) smin=s2;
                    if(smin>s3) smin=s3;

                SolutieD(st,dr);
                for(i=st; i<=dr; i++)
                    if(abs(v[st].x-v[i].x)<=smin) y.push_back(v[i]);


 }


}


int main()
{

f>>n;
for(i=1;i<=n;i++)
   {

    f>>X.x>>X.y;
v.push_back(X);
   }
sort(v.begin(),v.end(),comparare);
 //for(vector<punct> :: iterator it=v.begin() ; it!=v.end() ; ++it)
//    g<<it->x<<" ";

SolutieD(0,n-1);
SolutieS(0,n-1);
if(smin1<smin) smin=smin1;
if(smin2<smin) smin=smin2;

sort(y.begin(),y.end(),comp);

for(i=0; i<y.size(); i++)
    for(j=i+1; j<y.size() && j<=i+7; j++)
if(y[i].x!=y[j].x || y[i].y!=y[j].y)
{
    s=Euclid(y[i],y[j]);
    if(smin>s) smin=s;
}

g<<fixed<<setprecision(6)<<smin;

  f.close();
  g.close();


    return 0;
}