Pagini recente » Cod sursa (job #1171449) | Monitorul de evaluare | Cod sursa (job #1292814) | Cod sursa (job #19214) | Cod sursa (job #538898)
Cod sursa(job #538898)
#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+1), 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 ++] = v[i];
}
}
//sortare dupa Y a multimii de pcte aflate la distanta d de dreapta
// sort(p.begin(),p.begin()+p_size,comp) ;
//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 <= 6 ; 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;
}