Cod sursa(job #1472487)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 17 august 2015 09:50:42
Problema Cele mai apropiate puncte din plan Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define ll long long
#define MAX 100005
#define INF 4e18
#define x first
#define y second
#define pll pair<ll, ll>
using namespace std;
 
ifstream f("cmap.in") ;
ofstream g("cmap.out") ;
 
vector<pll> v(MAX), ordX, ordY;
 
ll dist(pll a, pll b){
	return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
 
ll sol(int s , int d){
	if (s >= d - 1)
  	return INF;
	if (d - s == 2){
  	if (ordY[s] > ordY[s + 1])
    	swap (ordY[s] , ordY[s + 1]);
  	return dist(ordX[s], ordX[s + 1]);
	}
 
	int mij = (s + d) / 2;
	ll best = min(sol(s, mij), sol(mij , d));
 
	merge(ordY.begin() + s, ordY.begin() + mij, ordY.begin() + mij, ordY.begin() + d, v.begin());
	copy(v.begin(), v.begin() + (d - s), ordY.begin() + s);
 
	int size = 0;
	for (int i = s ; i < d ; i++)
	if (abs(ordY[i].y - ordX[mij].x) <= best)
  	v[size ++] = ordY[i];
	for (int i = 0; i < size - 1 ; ++ i)
		for (int j = i + 1; j < size && j < i + 8 ; j++)
    	best = min(best, dist(v[i], v[j]));
	return best ;
}
 
int main(){
	int n;
	f >> n ;
	ordX.resize(n), ordY.resize(n);
	for (int i = 0; i < (int) ordX.size(); i++)
  	f >> ordX [i].x >> ordX [i].y;
 
	sort (ordX.begin(), ordX.end());
	for (int i = 0; i < (int) ordX.size(); i++)
  	ordY[i] = make_pair(ordX[i].y, ordX[i].x);
 
	g << fixed << setprecision(6) << sqrt (sol (0, n)) << "\n";
	return 0;
}