Cod sursa(job #969142)

Utilizator dropsdrop source drops Data 3 iulie 2013 16:38:12
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.07 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <bitset>
#include <queue>
#include <deque>
#include <list>
#include <set>
#include <ctime>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
using namespace std;
ifstream ff("cmap.in");
ofstream gg("cmap.out");

#define max 100001
int n, k;
struct per{ int x,y; per(int x0=0,int y0=0){x=x0;y=y0;} } ss[max], pp[max];
bool cmp(per a, per b){ return a.x==b.x?a.y<b.y:a.x<b.x; }
double dst(per a, per b){ return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y)); }

double sol(int s, int d){
	if(s>=d) return 0x3f3f3f3f;
	if(s==d-1) return dst(ss[s], ss[d]);
	int m=(s+d)/2;
	double r=min(sol(s,m),sol(m+1,d));
	k=0;
	for(int i=s;i<=d;i++)
	if(abs(ss[i].x-ss[m].x) <= r){
		pp[++k]=ss[i];
		for(int j=k-1;j>0 && k-j<=7;j--)
			r=min(r, dst(pp[k], pp[j]));
	}
	return r;
}
 
int main(){
	ff >> n;
	for(int i=0;i<n;i++) ff >> ss[i].x >> ss[i].y;
	sort(ss, ss+n, cmp);
	gg << setprecision(10) << fixed << sol(0,n-1) << "\n";
	return 0;
}