Pagini recente » Cod sursa (job #204631) | Rating Suneet Mahajan (ScarletS) | Monitorul de evaluare | Cod sursa (job #737568) | Cod sursa (job #2452214)
#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<fstream>
#include<iomanip>
#include<vector>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
const int N=1e5+5;
struct points{
int x,y;
};
bool cmpx(points a,points b){
if(a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
bool cmpy(points a,points b){
if(a.y==b.y)
return a.x<b.x;
return a.y<b.y;
}
double minn(double a,double b){
if(a<b)
return a;
return b;
}
vector<points> Px;
vector<points> Py;
double dist(points a,points b){
double distsq=(double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y);
distsq=(double)sqrt(distsq);
return distsq;
}
double abss(double x){
if(x>=0)
return x;
return -x;
}
double FindMinDist(const vector<points> &px,const vector<points> &py,int n){
double mindist;
if(n<=3){
mindist=dist(px[1],px[2]);
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
mindist=minn(mindist,dist(px[i],px[j]));
}
}
return mindist;
}
vector<points> pyl,pyr;
int lsz=0,rsz=0;
pyl.push_back({0,0});
pyr.push_back({0,0});
for(int i=1;i<=n;i++){
if(py[i].x<=px[n/2].x){
pyl.push_back(py[i]);
lsz++;
}
else{
pyr.push_back(py[i]);
rsz++;
}
}
double mindist1,mindist2;
mindist1=FindMinDist(px,pyl,lsz);
mindist2=FindMinDist(vector<points>(px.begin()+n/2,px.end()),pyr,rsz);
mindist=minn(mindist1,mindist2);
pyr.clear();
pyl.clear();
int nrs=0;
points strip[n+2];
for(int i=1;i<=n;i++){
if(abss(((double)px[n/2].x-py[i].x))<=mindist){
strip[++nrs]=py[i];
}
}
for(int i=1;i<=nrs;i++){
int j=i+1;
while(j<=nrs && strip[j].y-strip[i].y<=mindist){
mindist=minn(mindist,dist(strip[j],strip[i]));
j++;
}
}
return mindist;
}
int main()
{
int n;
fin>>n;
Px.resize(n+5);
Py.resize(n+5);
//scanf("%d",&n);
for(int i=1;i<=n;i++){
fin>>Px[i].x>>Px[i].y;
//scanf("%d%d",&Px[i].x,&Px[i].y);
Py[i]=Px[i];
}
sort(Px.begin()+1,Px.begin()+n+1,cmpx);
sort(Py.begin()+1,Py.begin()+n+1,cmpy);
//cout<<FindMinDist(Px,Py,n);
fout<<setprecision(100)<<FindMinDist(Px,Py,n);
return 0;
}