Pagini recente » Cod sursa (job #4940) | Profil Arkiny | Cod sursa (job #113800) | Profil YouDontNeedMyName | Cod sursa (job #1330762)
#include<fstream>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
const long long INF=(1LL<<31);
struct Point{
int x;
int y;
};
bool cmpX(Point i, Point j){
if(i.x == j.x)
return i.y < j.y;
else
return i.x < j.x;
}
bool cmpY(Point i, Point j){
if(i.y == j.y)
return i.x < j.x;
else
return i.y < j.y;
}
Point Px[1000],Py[1000], Pm[1000];
int PmSize;
long double globalMinDist=INF;
long double dist(Point i, Point j){
return sqrt(1LL*(i.x-j.x)*(i.x-j.x) + 1LL*(i.y - j.y)*(i.y - j.y));
}
long double brute(Point P[], int n){
long double d=INF;
for(int i=0; i< n-1; ++i)
for(int j=i+1; j<n; ++j)
d=min(d,dist(P[i],P[j]));
return d;
}
void distMinMij(){
for(int i=0; i<PmSize; ++i){
for(int j=i+1; j<PmSize && (Pm[j].y - Pm[i].y)< globalMinDist; ++j)
globalMinDist=min(globalMinDist , dist(Pm[i], Pm[j]));
}
}
long double distMin(Point Px[], Point Py[], int n){
if(n <= 3){
return brute(Px,n);
}
int mid=n/2;
Point midPoint=Px[mid];
Point Pyl[mid+1];
Point Pyr[n-mid];
int lp=0, rp=0;
for(int i=0; i<n; ++i){
if(Py[i].x <= midPoint.x)
Pyl[lp++] = Py[i];
else
Pyr[rp++] = Py[i];
}
globalMinDist = min(globalMinDist ,min(distMin(Px, Pyl, mid) , distMin(Px + mid, Pyr, n - mid)));
PmSize = 0;
for(int i = 0; i<n; ++i){
if(abs(Py[i].x - midPoint.x) < globalMinDist){
Pm[PmSize++] = Py[i];
}
}
return globalMinDist;
}
int main(){
int n,i,j;
Point p;
f>>n;
for(i=0; i<n; ++i){
f>>p.x>>p.y;
Px[i]=p;
Py[i]=p;
}
sort(Px, Px + n, cmpX);
sort(Py, Py + n, cmpY);
g<<fixed;
g.precision(10);
g<<distMin(Px , Py, n);
return 0;
}