Cod sursa(job #1860199)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 27 ianuarie 2017 22:12:30
Problema Cele mai apropiate puncte din plan Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 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<ll, ll> 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;}
pii jeg[NMAX];

double solve(int st, int dr, pii aux[]) {
	if(dr-st<=1) return INF;
	if(dr-st==2) {
		if(aux[st].second>aux[st+1].second) swap(aux[st],aux[st+1]);
		return dist(p[st],p[st+1]);
	}
	else if(dr-st==3) {
		sort(aux+st,aux+dr,compy);
		return min(dist(p[st],p[st+1]),min(dist(p[st],p[st+2]),dist(p[st+2],p[st+1])));
	}
	int mid=(st+dr)/2,i,j,pos=st,ind1,ind2;
	double delta=solve(st, mid,aux);
	delta=min(delta,solve(mid, dr,aux));

	merge(aux,aux+mid,aux+mid,aux+dr,jeg+st,compy);
	for(i=st;i<dr;++i) aux[i]=jeg[i];

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

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

	return delta;
}

int main() {
	int i;

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

	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;
}