Pagini recente » Cod sursa (job #2851933) | Cod sursa (job #71699) | Cod sursa (job #2870428) | Cod sursa (job #2710944) | Cod sursa (job #1546757)
#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("cmap.in");
ofstream out("cmap.out");
struct Point
{
long long x,y;
Point(int x= 0,int y = 0 )
{
x = this->x;
y = this->y;
}
};
long double distance(long long xa, long long ya , long long xb, long long yb)
{
long double res = sqrt( (xb - xa)*(xb - xa) + (yb - ya)*(yb - ya));
return res;
}
Point X[100003],Y[100003];
long double distanceBetweenClosestPairofPoints(int st,int dr)
{
if( dr - st + 1 > 3)
{
int mij = (st+dr)/2;
long double mins,mind,minm;
mins = distanceBetweenClosestPairofPoints(st,mij);
mind = distanceBetweenClosestPairofPoints(mij+1,dr);
minm = min(mins,mind);
int mergeSize = dr-st+1;
Point Merged[mergeSize+2];
int i = st;
int j = mij+1;
int p = 0;
while(i <= mij && j <= dr)
if (Y[i].y <= Y[j].y)
Merged[ ++ p ] = Y[ i ++ ];
else
Merged[ ++ p ] = Y[ j ++ ];
while(i <= mij )
Merged[ ++ p ] = Y[ i ++ ];
while( j <= dr )
Merged[ ++ p ] = Y[ j ++ ];
for(int i = st, j = 1 ; i <= dr ; i++,j++)
Y[i] = Merged[j];
for(int i = st ; i <= dr ; i++)
for(int j = 1 ; j <= 7 && i+j <= dr && Y[i+j].y - Y[i].y <= minm +0.001 ; j++)
minm = min( distance(Y[i].x, Y[i].y, Y[i+j].x, Y[i+j].y), minm);
return minm;
}
else
{
for(int i = st ; i< dr ; i++)
for(int j = st+1 ; j <= dr ; j++)
if (Y[i].y>Y[j].y)
swap(Y[i],Y[j]);
long double d = distance(X[st].x,X[st].y,X[st+1].x,X[st+1].y);
for(int i = st ; i< dr ; i++)
for(int j = i+1 ; j <= dr; j++)
d = min(distance(X[i].x,X[i].y,X[j].x,X[j].y),d);
return d;
}
}
int main()
{
int n;
in>>n;
for(int i = 1 ; i <= n ; i++)
in>>X[i].x>>X[i].y,Y[i] = X[i];
sort(X+1,X+n+1,[](Point a,Point b)
{
if (a.x < b.x)
return true;
else
{
if (a.x ==b.x)
if (a.y <= b.y)
return true;
else
return false;
return false;
}
});
out<<setprecision(6)<<fixed<<distanceBetweenClosestPairofPoints(1,n);
return 0;
}