Cod sursa(job #538900)

Utilizator c_adryanChitescu Adrian c_adryan Data 22 februarie 2011 01:04:00
Problema Cele mai apropiate puncte din plan Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 2.06 kb
#include <iostream>
#include <vector>
#include <cmath>
#include <utility>
#include <fstream>
#include <algorithm>
#include <iomanip>
#define inf 4e18 
using namespace std;

typedef  pair <long long,long long> point;
const int MAX_N = 100005;

vector<point> p(MAX_N),y;


// functie comparator pentru sortarea vectorului dupa Y
bool comp( point a , point b ) { 
	if( a.second == b.second ) 
		return a.first > b.first ;
	else
		return a.second > b.second ;		

}
//distanta dintre 2 puncte
double dist( point &a ,  point &b) {
	return sqrt( pow((double)(a.first - b.first),2.0) + pow((double)(a.second-b.second),2.0));
}


//distanta minima
double dist_min( int st, int dr , vector<point> &v) {
	if( dr - st <= 2) 
		if( dr == st +2 ) { // 3 puncte
					double mini = dist ( v[st],v[st+1]);
					double d2 = dist ( v[st],v[st+2]);
					double d3 = dist ( v[st+1],v[st+2]);
					mini = min( mini , min( d2 , d3));
					return mini;
	
			}
		else if( st == dr - 1 ) { // sunt doar 2 puncte => distanta dintre ele
				return dist( v[st], v[st+1] ) ;
		}	

	
	int m 		= (st + dr ) /2 ; // dreapta l dupa care se imparte multimea in P1,P2
	double d 	= min( dist_min(st, m,v) , 
						dist_min( (m), dr , v) );
	
	merge(y.begin()+st , y.begin() +m , y.begin() + m , y.begin()+ dr,
	 	p.begin(), comp);
	copy ( v.begin() , v.begin()+ (dr-st) , y.begin() + st);
	//determinare multime puncte care se afla la distanta d de dreapta	
	int p_size = 0;
	for( int i = st ; i < dr; i ++) {
		if( abs( (double) (y[i].first - v[m].first )) < d ){
			p[ p_size ++] = y[i];
		}
	}	
	
	//determinare distanta minima  cu puncte din cele 2 multimi P1 , P2
	for( int i  = 0 ,j; i < p_size -1  ; i++){
		for( j = i+1 ; j< p_size && j-i <= 8 ; j++)
			d = min( d , dist(p[j],p[i]) );
	
	}
	return d;

}

int main(){
	ifstream f("cmap.in");
	ofstream g("cmap.out");
	long n;
	f >> n;
	vector < point > v;
	v.resize( n );
	y.resize( n ) ;
	for( int i = 0 ; i < n; i++ ) {
		f>> v[i].first >> v[i].second;
		y[i] = v[ i ] ;
	}
	
	sort(v.begin(),v.end());
	g.setf(ios::fixed,ios::floatfield);
	g<< dist_min(0,n,v);

	g.close();
	return 0;
}