Pagini recente » Cod sursa (job #623323) | Cod sursa (job #1775452) | Cod sursa (job #2138095) | Cod sursa (job #2631496) | Cod sursa (job #3145289)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
ll get_distance(pair<ll,ll> A, pair<ll,ll> B){
return (A.first-B.first)*(A.first-B.first)+
(A.second-B.second)*(A.second-B.second);
}
ll bruteforce(vector<pair<ll,ll>> points, int st, int dr){
ll minim = LLONG_MAX;
for(int i=st;i<=dr;i++) for(int j=i+1;j<=dr;j++){
minim=min(minim, get_distance(points[i],points[j]));
}
return minim;
}
ll find_closest(vector<pair<ll,ll>> x_sorted, vector<pair<ll,ll>> y_sorted, int st, int dr){
if(dr-st+1<=3)
return bruteforce(x_sorted, st, dr);
int mid=(st+dr)/2;
ll dist=min(find_closest(x_sorted,y_sorted,st,mid),find_closest(x_sorted,y_sorted,mid+1,dr));
sort(y_sorted.begin()+st,y_sorted.begin()+dr+1);
vector<pair<ll,ll>> points(dr-st+1);
int len=0;
for(int i=st;i<=dr;i++){
if((y_sorted[i].second-x_sorted[mid].first)*(y_sorted[i].second-x_sorted[mid].first)<=dist)
points[len++]=y_sorted[i];
}
for(int i=0;i<len;i++){
for(int j=i+1;j<len && (points[j].second-points[i].second)*(points[j].second-points[i].second)<=dist;j++){
dist=min(dist, get_distance(points[i],points[j]));
}
}
return dist;
}
void solve(){
ifstream fin("cmap.in");
ofstream fout("cmap.out");
int N; fin>>N;
vector<pair<ll,ll>> x_sorted(N);
vector<pair<ll,ll>> y_sorted(N);
for(int i=0;i<N;i++)
fin>>x_sorted[i].first>>x_sorted[i].second;
sort(x_sorted.begin(), x_sorted.end());
for(int i=0;i<N;i++)
y_sorted[i]={x_sorted[i].second, x_sorted[i].first};
fout<<fixed<<setprecision(10)<<sqrt(find_closest(x_sorted, y_sorted, 0, N-1));
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
solve();
return 0;
}