Pagini recente » Cod sursa (job #2711630) | Cod sursa (job #2266213) | Cod sursa (job #573981) | Cod sursa (job #699603) | Cod sursa (job #2166062)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct punct
{
double x, y;
}p[100001];
int n;
double dist(punct a, punct b)
{
return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));
}
bool cmp(punct a, punct b)
{
return (a.x<b.x)||(a.x==b.x && a.y<b.y);
}
double closestStrip(int strip[], int n, double d)
{
double ans=d;
sort(strip+1, strip+n+1);
for(int i=1; i<=n; ++i)
{
for(int j=i+1; j<=n; ++j)
{
if(p[strip[j]].y-p[strip[i]].y>=d) break;
ans=min(ans, dist(p[strip[i]], p[strip[j]]));
}
}
return ans;
}
double divide(int st, int dr)
{
if(dr-st<2)
{
double answer=2e9 + 2;
for(int i=st; i<dr; ++i)
{
for(int j=i+1; j<=dr; ++j)
{
answer=min(answer, dist(p[i], p[j]));
}
}
return answer;
}
int m=(st+dr)/2;
double d=divide(st, m);
d=min(d, divide(m+1, dr));
int strip[100001];
int j=0;
for(int i=st; i<=dr; ++i)
{
if(abs(p[m].x-p[i].x)<2)
{
++j;
strip[j]=i;
}
}
return min(d, closestStrip(strip, j, d));
}
int main()
{
fin>>n;
for(int i=1; i<=n; ++i) fin>>p[i].x>>p[i].y;
sort(p+1, p+n+1, cmp);
fout<<fixed<<divide(1, n);
return 0;
}