Pagini recente » Cod sursa (job #819070) | Cod sursa (job #3216158) | Cod sursa (job #1666975) | Cod sursa (job #1821638) | Cod sursa (job #1770352)
#include <fstream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <iomanip>
#define inf 2e9
using namespace std;
ofstream g("cmap.out");
int n, i, j;
double m, s[100005], mn=inf;
struct point{
double x, y;
}v[100001];
bool comp(point a,point b)
{
if (a.x==b.x)
return a.y<b.y;
return a.x<b.x;
}
double dist(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool comp2(point a,point b)
{
if (a.y == b.y)
return a.x < b.x;
return a.y < b.y;
}
double Min(int st,int dr)
{
if (dr==st)
return inf;
if (dr==st+1)
return dist(v[st],v[dr]);
vector <point> A, B;
//double m = (s[dr] - s[st-1]) / ((dr-st)+1.0);
int i = (st+dr)/2;
//double m = v[i].x;
/*while (v[i].x < m && i < n)
i++;
if (i==st)
i++;*/
double d1, d2;
d1 = Min(st, i-1);
d2 = Min(i, dr);
mn = min(d1,min(mn, d2));
int sav = i-1;
while (m - v[sav].x < mn && sav > 0)
{
A.push_back(v[sav]);
sav--;
}
sav = i;
while (v[sav].x - m < mn && sav <= n)
{
B.push_back(v[sav]);
sav++;
}
sort (A.begin(),A.end(),comp2);
sort (B.begin(),B.end(),comp2);
int j = 0;
if (B.size() != 0 && A.size() != 0)
{
i=0;
for (i; i < A.size(); i++)
{
while (j+1 < B.size() && B[j+1].y<A[i].y)
j++;
sav = j;
while (sav >= 0 && abs(B[sav].y-A[i].y) < mn)
{
double x = dist(B[sav],A[i]);
if (x<mn)
mn=x;
sav--;
}
sav = j;
while (sav + 1 < B.size() && abs(B[sav+1].y-A[i].y) < mn)
{
sav++;
double x = dist(B[sav],A[i]);
if (x<mn)
mn=x;
}
}
}
return mn;
}
int main()
{
freopen("cmap.in","r",stdin);
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%lf%lf", &v[i].x, &v[i].y);
sort(v+1,v+n+1,comp);
/* for (int i = 1; i <= n; i++)
s[i]=s[i-1]+v[i].x;
m = s[n] / (n + 0.0);*/
g<<fixed;
g<<setprecision(6)<<Min(1,n);
return 0;
}