Cod sursa(job #611400)

Utilizator proflaurianPanaete Adrian proflaurian Data 1 septembrie 2011 13:58:48
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<cstdio>
#include<algorithm>
#include<cmath>
#define INF 1000000000.0
#define EPS 0.0000000001
using namespace std;
struct point{double X,Y;point(double x,double y){X=x;Y=y;};point(){X=0;Y=0;}};
point A[100010],B[100010];
double operator>(point,point);
int n,comp(point,point);
double x,y,CMAP(int, int);
void read(),solve();
int main()
{
	freopen("cmap.in","r",stdin);freopen("cmap.out","w",stdout);scanf("%d",&n);
	for(int i=1;i<=n;i++){scanf("%lf%lf",&x,&y);A[i]=point(x,y);}
	sort(A+1,A+n+1,comp);printf("%.6lf",CMAP(1,n+1));return 0;
}
double CMAP(int lo, int hi)
{
	double LO,HI,MI;int i,j,k,mi;
	if(hi==lo)return INF;if(hi-lo==1)return A[lo]>A[hi];
	mi=(lo+hi)>>1;LO=CMAP(lo,mi);HI=CMAP(mi,hi);MI=LO<=HI?LO:HI;
	for(i=lo,k=0;i<hi;i++){if(A[i].X-A[mi].X>MI)continue;if(A[mi].X-A[i].X>MI)continue;B[++k]=A[i];}
	for(i=1;i<=k;i++)for(j=i+1;j<=k&&j-i<=7;j++)MI=min(MI,B[i]>B[j]);
	return MI;
}
double operator>(point U, point V){return sqrt((U.X-V.X)*(U.X-V.X)+(U.Y-V.Y)*(U.Y-V.Y));}
int comp(point U,point V){if(V.X-U.X>EPS)return 1;if(U.X-V.X>EPS)return 0;if(V.Y-U.Y>EPS)return 1;return 0;}