Cod sursa(job #1222587)

Utilizator Luncasu_VictorVictor Luncasu Luncasu_Victor Data 23 august 2014 18:05:46
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <iomanip>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX 100010

struct Point{
	int X, Y;
} P[MAX];
int N;	

bool PCmp(Point A, Point B){
	return A.X < B.X;
}

double Dist(Point A, Point B) {
	return sqrt((A.X-B.X) * (A.X-B.X) + (A.Y - B.Y) * (A.Y - B.Y));
}

double Divide(int L, int R) {
	if (R - L + 1 <= 3) {
		return min(Dist(P[L], P[L+1]), min(Dist(P[L], P[L+2]), Dist(P[L+1], P[L+2])));
	} else {
		int M = (L + R) / 2;
		double S = min(Divide(L, M), Divide(M, R)), S1;
		S1 = S;
		for (int i = M; i >= L && P[M].X - P[i].X <= S; i--)
			for (int j = 1; j <= 7 && i+j <= R; j++) {
				S1 = min(S1, Dist(P[i], P[i+j]));
			}
		return S1;
	}
}

int main() {
	int X, Y;

	freopen("cmap.in","r",stdin);
	freopen("cmap.out","w",stdout);

	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		scanf("%d %d", &P[i].X, &P[i].Y);
	}
	sort(P+1, P+N+1, PCmp);
	cout << setprecision(8) << fixed << Divide(1, N);

	return 0;
}