Pagini recente » Istoria paginii runda/problemebarajgimnaziu/clasament | Cod sursa (job #1967870) | agm-2018/runda1 | Istoria paginii runda/vot/voteaza_miruna/clasament | Cod sursa (job #2983864)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Pct{
long double i, j;
}x[100001];
bool C(Pct a, Pct b)
{if(a.i<b.i || (a.i==b.i && a.j<b.j))return 1;
return 0;
}
bool C1(Pct a, Pct b)
{if(a.j<b.j || (a.j==b.j && a.i<b.i))return 1;
return 0;
}
long double Dist(int x1, int y1, int x2, int y2)
{long double a=sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
return a;
}
long double DQ(int st, int dr)
{if(dr-st+1<=3)
{long double mini=2000000000;
for(int i=st;i<dr;i++)
for(int j=i+1;j<=dr;j++)
mini=min(mini, Dist(x[i].i, x[i].j, x[j].i, x[j].j));
return mini;
}
else
{int mij=(st+dr)/2;
long double mini=min(DQ(st, mij), DQ(mij+1, dr));
vector<Pct> y;
for(int i=st;i<=dr;i++)
if(abs(x[i].i-x[mij].i)<=mini && i!=mij)y.push_back(x[i]);
sort(y.begin(), y.end(), C1);
for(int i=0;i<y.size()-1;i++)
for(int j=i+1;j<y.size() && j-i+1<=9;j++)
mini=min(mini, Dist(y[i].i, y[i].j, y[j].i, y[j].j));
return mini;
}
}
int main()
{ int n;
fin>>n;
for(int i=1;i<=n;i++)
fin>>x[i].i>>x[i].j;
sort(x+1, x+1+n, C);
fout<<fixed<<setprecision(6)<<DQ(1, n);
return 0;
}