Cod sursa(job #378879)

Utilizator GheorgheMihaiMihai Gheorghe GheorgheMihai Data 29 decembrie 2009 20:56:41
Problema Cele mai apropiate puncte din plan Scor Ascuns
Compilator cpp Status done
Runda Marime 1.68 kb
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <algorithm>
#define INF 2000000000
using namespace std;
ifstream fi("cmap.in");
int N;
struct punct { int x,y; }v[1000002];
int puncte[1000002];
int aux[1000002];

inline bool cmp(const int &x,const int &y){ return (v[x].x<v[y].x); }

inline int diffabs(int x,int y){
		if (x<y) return (y-x); else return (x-y);
}

double distp(punct p1, punct p2)
{
	return sqrt((double)((long long)((long long)p1.x-p2.x)*(p1.x-p2.x)+(long long)((long long)p1.y-p2.y)*(p1.y-p2.y)));
}

double dmin(int left,int right){
	if (left==right) return INF;
	int m=(left+right)/2;
	int part=v[puncte[m]].x;
	double d1=dmin(left,m),d2=dmin(m+1,right);
	double minim=min(d1,d2);
	int ind1=left,ind2=m+1,ind=left-1;
	while (ind1<=m || ind2<=right)
		if (ind1>m) { aux[++ind]=puncte[ind2];++ind2;}  else
			if (ind2>right) { aux[++ind]=puncte[ind1];++ind1; } else
				if (v[puncte[ind1]].y<v[puncte[ind2]].y) { aux[++ind]=puncte[ind1];++ind1; } 
					else { aux[++ind]=puncte[ind2];++ind2; }
	int np=0;
	for (int i=left;i<=right;++i) { 
		puncte[i]=aux[i];
		if ((part-(minim/2))<=v[puncte[i]].x && (part+(minim/2))>=v[puncte[i]].x) aux[++np]=puncte[i];
	}
	double dist=minim;
	for (int i=1;i<=np;++i)
		for (int j=i-1;(j>=1) && (j>=i-6);--j)
			dist=min(dist,distp(v[aux[i]],v[aux[j]]));//max(diffabs(v[aux[i]].x,v[aux[j]].x),diffabs(v[aux[i]].y,v[aux[j]].y)));
	return dist;
}

int main(){
	fi>>N;
	for (int i=1;i<=N;++i)
		fi>>v[i].x>>v[i].y;
	for (int i=1;i<=N;++i) puncte[i]=i;
	sort(puncte+1,puncte+N+1,cmp);
	double rez=dmin(1,N);
	freopen("cmap.out","w",stdout);
	printf("%lf\n",rez);
	fi.close();
	return 0;
}