Pagini recente » Cod sursa (job #36253) | Cod sursa (job #237433) | Cod sursa (job #2149066) | Cod sursa (job #2591821) | Cod sursa (job #2171258)
#include <bits/stdc++.h>
#define INFILE "cmap.in"
#define OUTFILE "cmap.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
typedef long long lint;
typedef pair<lint,lint> Point;
const int MAX_N = 100005;
const lint INF = 4e18;
lint dist(Point A, Point B){
return (A.first-B.first)*(A.first-B.first)+(A.second-B.second)*(A.second-B.second);
}
lint minDist(int st,int dr,vector<Point>&X,vector<Point>&Y){
if(st>=dr-1)
return INF;
if(dr-st==2){
if(Y[st]>Y[st+1])
swap(Y[st],Y[st+1]);
return dist(X[st],X[st+1]);
}
int mid=(st+dr)/2;
lint best=min(minDist(st,mid,X,Y),minDist(mid,dr,X,Y));
sort(Y.begin()+st,Y.begin()+dr);
vector<Point> V;
for(int i=st;i<dr;i++)
if(abs(Y[i].second-X[mid].first)<=best)
V.push_back(Y[i]);
for(int i=0;i<V.size();i++){
for(int j=i+1;j<V.size()&&(j-i)<8;j++){
best=min(best,dist(V[i],V[j]));
}
}
return best;
}
int main(){
int N;
in>>N;
vector<Point> X;
vector<Point> Y;
for(int i=1;i<=N;i++){
int x,y;
in>>x>>y;
X.push_back({x,y});
}
sort(X.begin(),X.end());
for(auto x:X){
Y.push_back({x.second,x.first});
}
out<<fixed<<setprecision(6)<<sqrt(minDist(0,X.size(),X,Y));
return 0;
}