Pagini recente » Cod sursa (job #899027) | Cod sursa (job #296802) | Cod sursa (job #2595161) | Cod sursa (job #2928984) | Cod sursa (job #2064865)
#include<algorithm>
#include<vector>
#include<fstream>
#include<iostream>
#include<cstdio>
#include<iomanip>.
#include<cmath>
#define NMAX 100000 + 5
#define INF 0xFFFFFFFFFFFFF
#define min(a,b) a < b ? a : b
using namespace std;
ifstream in("cmap.in");
class POINT
{
public :
double x,y;
friend bool mycompx(POINT a,POINT b);
friend bool mycompy(POINT a,POINT b);
friend double point_distance(POINT a, POINT b)
{
double lat_1 = b.x - a.x;
double lat_2 = b.y - a.y;
return sqrt(lat_1*lat_1 + lat_2*lat_2);
}
};
bool mycompy(POINT a,POINT b)
{
return a.y < b.y;
}
bool mycompx(POINT a,POINT b)
{
return a.x < b.x;
}
POINT v_sortedx[NMAX];
POINT v_sortedy[NMAX];
POINT strip[NMAX];
int n;
void read_data()
{
in >> n;
for(int i = 1 ; i<=n ; ++i)
{
in>>v_sortedx[i].x;
in>>v_sortedx[i].y;
v_sortedy[i].x = v_sortedx[i].x;
v_sortedy[i].y = v_sortedx[i].y;
}
}
double small_dist(int left,int right)
{
int i,j;
double dist = INF;
for(i = left ; i < right ; ++i)
for( j = i+1 ; j <=right ; ++j)
{
double temp = point_distance(v_sortedx[i],v_sortedx[j]);
if( temp < dist)
dist = temp;
}
return dist;
}
double min_distance(int left,int right)
{
if(right - left <= 4)
{
return small_dist(left,right);
}
int m = (left + right ) / 2;
double d1 = min_distance(left,m);
double d2 = min_distance(m,right);
double d = min(d1,d2);
int k = 0;
for(int i = left ; i<=right ; ++i)
{
if(point_distance(v_sortedx[i],v_sortedx[m]) < d)
strip[++k] = v_sortedx[i];
}
sort(strip+1,strip+k+1,mycompy);
for(int i = 1 ; i<=k ; ++i)
{
for(int j = i + 1; i-j <= 7 && j <=k ; ++j)
{
double dist = point_distance(strip[i],strip[j]);
if(dist < d)
d = dist;
}
}
return d;
}
int main()
{
read_data();
freopen("cmap.out","w",stdout);
sort(v_sortedx+1,v_sortedx+n+1,mycompx);
sort(v_sortedy+1,v_sortedy+n+1,mycompy);
double d;
d = min_distance(1,n);
printf("%.6lf",d);
return 0;
}