Cod sursa(job #1553435)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 19 decembrie 2015 20:49:31
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <vector>
#define MAX 100005
#define pdd pair<double,double>
#define x first
#define y second
using namespace std;

int n;
pdd l[MAX];

double dist2(pdd a, pdd b){
	return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

double dist(int s, int d){
	if(d - s == 2)
		return dist2(l[s], l[s + 1]);
	if(d - s == 3){
		double d1 = dist2(l[s], l[s + 1]);
		double d2 = dist2(l[s + 1], l[s + 2]);
		double d3 = dist2(l[s], l[s + 2]);
		double min = d1 < d2 ? d1 : d2;
		return min < d3 ? min : d3;
	}

	double xdr = l[(s + d) / 2].x;
	double r1 = dist(s, (s + d) / 2);
	double r2 = dist((s + d) / 2, d);
	double r = r1 < r2 ? r1 : r2;

	double rez = r;
	vector<pdd> Y;
	int poz = (s + d) / 2;
	while(poz >= s && xdr - l[poz].x <= r)
		poz--;
	poz++;
	while(poz < d && l[poz].x - xdr <= r)
		Y.push_back(l[poz++]);

	for(int i = 0; i < Y.size(); i++){
		if(Y[i].x > xdr)
			break;
		for(int j = i + 1; j < i + 8 && j < Y.size(); j++){
			double aux = dist2(Y[i], Y[j]);
			rez = aux < rez ? aux : rez;
		}
	}
	return  rez;
}

int main(){
	freopen("cmap.in", "r", stdin);
	freopen("cmap.out", "w", stdout);
	scanf("%d", &n);
	for(int i = 0; i < n; i++)
		scanf("%lf%lf", &l[i].x, &l[i].y);
	sort(l, l + n);
	printf("%lf\n", dist(0, n));
	return 0;
}