Cod sursa(job #2073516)

Utilizator MaarcellKurt Godel Maarcell Data 23 noiembrie 2017 11:47:16
Problema Cele mai apropiate puncte din plan Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <ctime>
#include <unordered_map>
#include <iomanip>
#include <complex>
#include <cassert>
using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define deb(a) cerr<< #a << "= " << (a)<<"\n";

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef long double ld;
typedef complex<double> base;
typedef vector<int> vi;
typedef pair<int,int> pii;

template<class T> ostream& operator<<(ostream& stream, const vector<T> v){ stream << "[ "; for (int i=0; i<(int)v.size(); i++) stream << v[i] << " "; stream << "]"; return stream; }
ll fpow(ll x, ll p, ll m){ll r=1; for (;p;p>>=1){ if (p&1) r=r*x%m; x=x*x%m; } return r;}
int gcd(int a, int b){ if (!b) return a; return gcd(b,a%b);}
ll gcd(ll a, ll b){ if (!b) return a; return gcd(b,a%b);}


struct point{
	int x,y;
	point(int x=0, int y=0) : x(x), y(y) {}
};

double dist(point A, point B){
	return sqrt(1LL*(A.x-B.x)*(A.x-B.x)+1LL*(A.y-B.y)*(A.y-B.y));
}

int N; point a[100100]; 
point v[100100]; int K;

double mind(int l, int r){
	if (r-l+1<=1) return (1LL<<30);
	if (r-l+1==2){
		if (a[l].y>a[r].y) swap(a[l],a[r]);
		return dist(a[l],a[r]);
	}
	
	double ans=(1LL<<30);
	int mid=(l+r)/2;
	ans=min(ans,mind(l,mid));
	ans=min(ans,mind(mid+1,r));
	
	
	int x=l,y=mid+1;
	K=0;
	
	while (x<=mid && y<=r){
		if (a[x].y<a[y].y) v[K++]=a[x],x++;
		else v[K++]=a[y],y++;
	}
	while (x<=mid) v[K++]=a[x],x++;
	while (y<=r) v[K++]=a[y],y++;
	
	int i,j;
	for (i=l; i<=r; i++)
		a[i]=v[i-l];
		
	for (i=l; i<=r; i++)
		for (j=i+1; j<=r && j-i<=8; j++)
			ans=min(ans,dist(a[i],a[j]));
	
	
	return ans;
}



int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	ifstream fin("cmap.in");
	ofstream fout("cmap.out");
	fin >> N;
	
	int i;
	for (i=1; i<=N; i++)
		fin >> a[i].x >> a[i].y;
	
	sort(a+1,a+N+1,[](point A, point B){return A.x<B.x; });
	fout << fixed << setprecision(10) << mind(1,N) << "\n";
	return 0;
}