Pagini recente » Cod sursa (job #1720280) | Cod sursa (job #882216) | Cod sursa (job #213359) | Cod sursa (job #481039) | Cod sursa (job #590643)
Cod sursa(job #590643)
#include <fstream>
#include <math.h>
#include <algorithm>
#include <iomanip>
#define INF 4e18
using namespace std;
int n,i,j,vs,ly2;
struct punct{long long x; long long y;};
punct x[100005],y[100005],v[100005],y2[100005];
int cmp(punct a,punct b)
{
if (a.x!=b.x)
return (a.x<b.x);
return (a.y<b.y);
}
inline void swap(punct &a,punct &b)
{
punct aux=a;
a=b;
b=aux;
}
long long dist(punct x,punct y)
{
return (x.x-y.x)*(x.x-y.x)+(x.y-y.y)*(x.y-y.y);
}
inline long long min(long long a,long long b)
{
if (a>b) return b;
return a;
}
long long apel(int st,int dr)
{
if (st>=dr-1) return INF;
if (dr-st==2)
{
if (y[st].x>y[st+1].x || (y[st].x==y[st+1].x && y[st].y>y[st+1].y))
swap(y[st],y[st+1]);
return dist(x[st],x[st+1]);
}
int m=(st+dr)/2;
long long best=min(apel(st,m),apel(m,dr));
i=st;
j=m;
ly2=st;
while (ly2<dr)
{
if (i>=m){y2[ly2]=y[j]; j++; ly2++;continue;}
if (j>=dr) {y2[ly2]=y[i]; i++; ly2++;continue;}
if (y[i].x>y[j].x || (y[i].x==y[j].x && y[i].y>y[j].y))
{y2[ly2]=y[j]; j++; ly2++;continue;}
y2[ly2]=y[i]; i++; ly2++;continue;
}
for (i=st;i<dr;i++)
y[i]=y2[i];
vs=0;
for (i=st;i<dr;i++)
if (abs(y[i].y-x[m].x)<=best)
v[++vs]=y[i];
for (i=1;i<=vs;i++)
{
for (j=i+1;j<=vs && j-i<=7;j++)
best=min(best,dist(v[i],v[j]));
}
return best;
}
int main(void)
{
ifstream f("cmap.in");
ofstream o("cmap.out");
f>>n;
for (i=1;i<=n;i++)
f>>x[i].x>>x[i].y;
sort(x+1,x+n+1,cmp);
for (i=1;i<=n;i++)
{
y[i].x=x[i].y;
y[i].y=x[i].x;
}
o<<fixed<<setprecision(6)<<sqrt(apel(1,n+1));
return 0;
}