Cod sursa(job #1860018)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 27 ianuarie 2017 21:01:22
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <cstdio>
#include <iostream>
#include <queue>
#include <vector>
#include <fstream>
#include <algorithm>
#include <string>
#include <iomanip>
#include <cstring>
#include <map>
#include <iomanip>
#include <stack>
#include <bitset>
#include <cctype>
#include <set>
#define MOD 9973
#define pb push_back
#define INF 0x3f3f3f3f
#define INFLL (1LL*INF*INF)
#define ll long long
#define NMAX 100005

using namespace std;

typedef pair<int, int> pii;

ifstream fin("cmap.in");
ofstream fout("cmap.out");

pii p[NMAX],aux[NMAX];
int n;

inline double dist(pii a, pii b) {
	return sqrt((a.first-b.first)*(a.first-b.first) + (a.second-b.second)*(a.second-b.second));
}

bool compy(pii a, pii b) {return a.second<b.second;}

double solve(int st, int dr, pii aux[]) {
	if(st>dr) return INF;
	if(dr-st<=2) return dist(p[st],p[st+1]);

	int mid=(st+dr)/2,i,j;
	double delta=min(solve(st, mid, aux),solve(mid, dr, aux));

	sort(aux+st+1,aux+dr+1,compy);

	vector<pii> v;
	for(i=st;i<dr;++i)
		if(abs(aux[i].second-p[mid].second)<=delta) v.pb(aux[i]);

	for(i=0;i<v.size();++i)
		for(j=i+1;j<v.size();++j)
			delta=min(delta,dist(v[i],v[j]));

	return delta;
}

int main() {
	int k,i,lg=1,dir;

	fin>>n;
	for(i=1;i<=n;++i) {
		fin>>p[i].first>>p[i].second;
		aux[i]=p[i];
	}

	sort(p+1,p+n+1);

	for(i=1;i<=n;++i) aux[i]=p[i];

	fout<<fixed<<setprecision(6)<<solve(1,n+1,aux);

	return 0;
}