Mai intai trebuie sa te autentifici.
Cod sursa(job #2071574)
Utilizator | Data | 20 noiembrie 2017 19:52:18 | |
---|---|---|---|
Problema | Cele mai apropiate puncte din plan | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.73 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream f("cmap.in.txt");
ofstream g("cmap.out.txt");
struct punct
{
int x,y;
};
long long distanta(punct p1, punct p2)
{
return pow((p1.x-p2.x),2)+pow((p1.y-p2.y),2);
}
bool comparX(punct p1,punct p2)
{
return p1.x<p2.x;
}
bool comparY(punct p1,punct p2)
{
return p1.y<p2.y;
}
long long DistantaMinima(vector<punct> &v,int stg,int dr)
{
int mijloc=(stg+dr)/2;
long long dist,distdr,diststg,delta;
int i,j;
vector<punct> temp;
if(dr-stg==1)
{
return distanta(v[stg],v[dr]);
}
if(dr-stg==2)
{
long long dist1,dist2,dist3;
dist1=distanta(v[stg],v[dr]);
dist2=distanta(v[stg+1],v[dr]);
dist3=distanta(v[stg],v[stg+1]);
return min(dist1,min(dist2,dist3));
}
diststg=DistantaMinima(v,stg,mijloc);
distdr=DistantaMinima(v,mijloc+1,dr);
dist=min(diststg,distdr);
delta=(int) ceil(sqrt(dist));
for(i=stg;i<=dr;i++)
{
if(abs(v[i].x-v[mijloc].x)<=delta)
{
temp.push_back(v[i]);
}
}
sort(temp.begin(),temp.end(),comparY);
for(i=0; i<temp.size(); i++)
{
for(j=i+1; j<=i+7 && j<temp.size(); j++)
{
dist=min(dist,distanta(temp[i],temp[j]));
}
}
return dist;
}
int main()
{
int n,i,x,y;
vector<punct> v;
punct p;
f>>n;
for(i=0;i<n;i++)
{
f>>p.x>>p.y;
v.push_back(p);
}
sort(v.begin(),v.end(),comparX);
g<<fixed<<setprecision(6)<<sqrt(DistantaMinima(v,0,n-1));
f.close();
g.close();
return 0;
}