Pagini recente » Cod sursa (job #2786257) | Cod sursa (job #2200828) | Cod sursa (job #2737094) | Cod sursa (job #2114357) | Cod sursa (job #2070902)
#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{
long long 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){
return (a.x - b.x )*(a.x - b.x ) + ( a.y - b.y )*( a.y - b.y );
}
//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
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]);
}
}
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;
}