Cod sursa(job #2054878)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 2 noiembrie 2017 17:13:43
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.69 kb
#include <bits/stdc++.h>
#define NMAX 100005
#define x first
#define y second

using namespace std;

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

pair<int, int> v[NMAX], aux[NMAX], local[NMAX];

inline double dist(pair<int, int> A, pair<int, int> B) {
	return sqrt(1LL*(A.x-B.x)*(A.x-B.x)+1LL*(A.y-B.y)*(A.y-B.y));
}

bool comp(pair<int, int> A, pair<int, int> B) {
	return B.y > B.x;
}

double solve(int left, int right) {
	if(right - left == 1) {
		if(aux[left].y > aux[right].y)
			swap(aux[left], aux[right]);

		return dist(aux[left], aux[right]);
	}
	else if(right - left == 2) {
		sort(aux+left, aux+right+1, comp);

		return min(dist(aux[left], aux[left+1]), min(dist(aux[left+1], aux[left+2]), dist(aux[left], aux[left+2])));
	}

 	int mid=(left+right)/2,ind1=left,ind2=mid+1,ind=left,i,j;
	double x = solve(left, mid);
	double y = solve(mid+1, right);
	double d=min(x, y);

	while(ind1 <= mid && ind2 <=right) {
		if(aux[ind1].y < aux[ind2].y)
			local[ind++] = aux[ind1++];
		else local[ind++] = aux[ind2++];
	}

	while(ind1<=mid)
		local[ind++]=aux[ind1++];

	while(ind2<=right)
		local[ind++]=aux[ind2++];

	for(i=left;i<=right;++i) aux[i]=local[i];

	vector<pair<int, int> > candidates;
	for(i=left;i<=right;++i)
		if(abs(aux[i].first-v[mid].first)<=d)
			candidates.push_back(aux[i]);

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

	return d;
}

int main() {
	int n,i;

	fin>>n;

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

	sort(v+1,v+n+1);
	for(i=1;i<=n;++i) aux[i]=v[i];

	fout<<fixed<<setprecision(6)<<solve(1,n)<<'\n';

	return 0;
}