Cod sursa(job #1721855)

Utilizator valentin50517Vozian Valentin valentin50517 Data 26 iunie 2016 17:07:22
Problema Cele mai apropiate puncte din plan Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.8 kb
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<ll,ll> pll;
pll A[100100],X[100100],Y[100100];
ll N;
ll dist(pll a,pll b){return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}
ll rez(int st,int dr){
	if(st >= dr-1) return LLONG_MAX;
	if(dr-st == 2) return dist(X[st],X[st+1]);
	int mid = (st+dr)/2;
	ll best = rez(st,mid)+rez(mid,dr);
	sort(Y + st,Y + dr);
	for(int i = st;i<dr-1;i++)
		for(int j = i+1; j<dr-1 && j-i < 8;j++) best = min(best,dist(Y[i],Y[j]));
	return best;
}
int main(){
	ifstream cin("cmap.in");
	ofstream cout("cmap.out");
	cin >> N;
	for(int i = 0;i<N;i++){cin >> A[i].x >> A[i].y; X[i] = A[i];}
	sort(X,X+N);
	for(int i = 0;i<N;i++) Y[i] = make_pair(X[i].y,X[i].x);
	cout << fixed << setprecision(10) << sqrt(rez(0,N));
	return 0;
}