Cod sursa(job #716413)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 18 martie 2012 19:17:50
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector> 
using namespace std;

struct point{long long x, y;};

long long d(point a, point b){
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y); 
}

bool Compare(point a, point b){
	if (a.x == b.x) return a.y < b.y;
	return a.x < b.x;
}

vector <point> v;

long long Dist(int l, int r){
	if (r - l == 1) return d(v[l], v[r]);
	long long i, j, q, dL, dR, m = (l + r) / 2;
	dL = Dist(l, m);
	dR = Dist(m, r);
	q = min(dL, dR);
	
	for (i = m - 1; i >= l && abs(v[m].x - v[i].x) <= sqrt(q); i--)
			for (j = i + 1; j < i + 8 && j <= r; j++)
				q = min(d(v[i], v[j]), q) ;
	for (i = m + 1; i <= r && abs(v[m].x - v[i].x) <= sqrt(q); i++)
			for (j = i + 1; j < i + 8 && j <= r; j++)
				q = min(d(v[i], v[j]), q) ;
	return q;
}

int main(){
	freopen("cmap.in", "r", stdin), freopen("cmap.out", "w", stdout);
	int n, i;
	scanf("%d", &n);
	v.resize(n);
	
	for (i = 0; i < n; i++)
		scanf("%lld %lld", &v[i].x, &v[i].y);
		
	sort(v.begin(), v.end(), Compare);
	printf("%lf", sqrt(Dist(0, n - 1)));
}