Pagini recente » Cod sursa (job #322630) | Cod sursa (job #389288) | Cod sursa (job #1433878) | Cod sursa (job #225165) | Cod sursa (job #2070885)
#include<iostream>
#include<fstream>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
#define Nmax 100100
struct point{
int x, y;
}v[Nmax],w[Nmax];
int n;
bool cmp_x (point a, point b){
return a.x < b.x;
}
bool cmp_y(point a, point b){
return a.y < b.y;
}
long long dist ( point a, point b){
long long difx = 1LL * (a.x - b.x );
long long dify = 1LL * ( a.y - b.y );
return difx * difx + dify * dify ;
}
//int coord_x1,coord_y1,coord_x2,coord_y2;
//long long dmin=Nmax;
long long divide ( int left, int right){
if( right - left == 1){//2 puncte
/*if(dist( v[left], v[right] )<dmin){
coord_x1=v[left].x;
coord_y1=v[left].y;
coord_x2=v[right].x;
coord_y2=v[right].y;
}*/
return dist( v[left], v[right] );
}
if ( right-left == 2 ){//3 puncte
//return min(dist(v[left], v[left+1]),min(dist(v[left+1], v[right]),dist(v[left], v[right])));
long long x,y,z;
x=dist(v[left], v[left+1]);
y=dist(v[left+1], v[right]);
z=dist(v[left], v[right]);
if((x<y)&&(x<z)){
/*if(x<dmin){
coord_x1=v[left].x;
coord_y1=v[left].y;
coord_x2=v[left+1].x;
coord_y2=v[left+1].y;
}*/
return x;
}
if((y<x)&&(y<z)){
/*if(y<dmin){
coord_x1=v[left+1].x;
coord_y1=v[left+1].y;
coord_x2=v[right].x;
coord_y2=v[right].y;
}*/
return y;
}
if((z<x)&&(z<y)){
/*if(z<dmin)
coord_x1=v[left].x;
coord_y1=v[left].y;
coord_x2=v[right].x;
coord_y2=v[right].y;*/
return z;
}
}
int m=( left + right ) / 2;
long long d1 = divide ( left, m ) ;
long long d2 = divide ( m+1, right ) ;
long long d = min( d1, d2);
int i,j,k=0;
long long delta = ceil(sqrt(d));
for( i = left; i <= right; i++){
if( abs( v[i].x - v[m].x ) <= delta ){
w[k].x = v[i].x;
w[k].y = v[i].y;
k++;
}
}
sort(w,w+k,cmp_y);
for(i = 0;i < k ; i++)
for(j = i + 1 ; j <= (i+7) && j < k; j++){
if(dist(w[i],w[j])<d){
/*coord_x1=w[i].x;
coord_y1=w[i].y;
coord_x2=w[j].x;
coord_y2=w[j].y;*/
d=dist(w[i],w[j]);
}
//d=min(d,dist(w[i],w[j]))
}
return d;
}
int main(){
int n;
f>>n;
for (int i =0;i<n;i++)
f>>v[i].x>>v[i].y;
sort(v,v+n,cmp_x);
g<<fixed<<setprecision(6)<<sqrt(divide(0,n-1));
f.close();
g.close();
/*g<<coord_x1<<" "<<coord_y1<<endl;
g<<coord_x2<<" "<<coord_y2<<endl;*/
return 0;
}