Pagini recente » Cod sursa (job #1822572) | Cod sursa (job #780205) | Cod sursa (job #2521081) | Cod sursa (job #73272) | Cod sursa (job #717374)
Cod sursa(job #717374)
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#define INF 2305843009213693942
#define type long long
#define PI pair<type,type>
#define MP make_pair
#define PB push_back
#define x first
#define y second
#define SZ size()
#define BG begin()
#define ED end()
#define NMAX 100010
using namespace std;
ifstream f("cmap.in");
ofstream g("cmap.out");
vector<PI> V(NMAX),X,Y;
type n,i,ra,rb;
type Dist(PI a,PI b) {return ((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
type MinDist(int left,int right,vector<PI> &X,vector<PI> &Y) {
if (left+1>=right) return INF;
if (right-left==2) {
if (Y[left]>Y[left+1]) swap(Y[left],Y[left+1]);
return Dist(X[left],X[left+1]);
}
int middle=(left+right)/2;
type ANS=min(MinDist(left,middle,X,Y),MinDist(middle,right,X,Y));
merge(Y.BG+left,Y.BG+middle,Y.BG+middle,Y.BG+right,V.BG);
copy(V.BG,V.BG+(right-left),Y.BG+left);
V.clear();
for (int i=left;i<right;i++)
if (abs(Y[i].y-X[middle].x)<=ANS)
V.PB(Y[i]);
for (int i=0;i<V.SZ;i++)
for (int j=i+1;j<V.SZ && j<i+4;j++)
ANS=min(ANS,Dist(V[i],V[j]));
return ANS;
}
int main() {
f >> n;
for (i=0;i<n;i++) {
f >> ra >> rb;
X.PB(MP(ra,rb));
Y.PB(MP(rb,ra));
}
sort(X.begin(),X.end());
g << fixed << setprecision(8) << sqrt((double)MinDist(0,X.size(),X,Y)) << '\n';
f.close();g.close();
return 0;
}