Cod sursa(job #658143)

Utilizator swift90Ionut Bogdanescu swift90 Data 7 ianuarie 2012 23:49:47
Problema Cele mai apropiate puncte din plan Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include<cstdio>
#include<fstream>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const long long INF=(1LL<<63)-1;
struct punct{
	int x,y;
}nr[100100], pct[100100];
struct cmpx{
	bool operator()(punct a,punct b){
		if(a.x<b.x)
			return true;
		return false;
	}
};
struct cmpy{
	bool operator()(punct a,punct b){
		if(a.y<b.y)
			return true;
		return false;
	}
};

int N,P;
long long dist(long long x1,long long y1, long long x2, long long y2){
	return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}
long long modul(long long x){
	if(x<0)
		return -x;
	return x;
}
long long solve(int st,int dr){
	long long dmin=INF,d;
	if(dr-st<=3){
		if(dr-st>0)
			dmin=dist(nr[st].x,nr[st].y,nr[st+1].x,nr[st+1].y);
		if(dr==st+2){
			d=dist(nr[st].x,nr[st].y,nr[st+2].x,nr[st+2].y);
			if(d<dmin)
				dmin=d;
			d=dist(nr[st+1].x,nr[st+1].y,nr[st+2].x,nr[st+2].y);
		}
		return dmin;
	}
	int i,j,u,mij=(st+dr)>>1;
	dmin=solve(st,mij);
	d=solve(mij+1,dr);
	if(d<dmin)
		dmin=d;
	
	P=-1;
	for(i=st;i<=dr;++i){
		if(modul(nr[i].x-nr[mij].x)<=dmin)
			pct[++P]=nr[i];
	}
	sort(pct,pct+P,cmpy());
	
	for(i=1,u=0;i<P;++i){
		while(pct[i].y-pct[u].y>=dmin)
			++u;
		for(j=u;j<i;++j){
			d=dist(pct[i].x,pct[i].y,pct[j].x,pct[j].y);
			if(d<dmin)
				dmin=d;
		}
	}
	return dmin;
}
int main(){
	//freopen("cmap.in","r",stdin);
	ifstream f("cmap.in");
	freopen("cmap.out","w",stdout);
	int i;
	//scanf("%d",&N);
	f>>N;
	for(i=1;i<=N;++i)
		//scanf("%d%d",&nr[i].x,&nr[i].y);
		f>>nr[i].x>>nr[i].y;
	sort(nr+1,nr+N+1,cmpx());
	
	printf("%.6f\n",sqrt(solve(1,N)));
	fclose(stdin);
	fclose(stdout);
	return 0;
}