Pagini recente » Cod sursa (job #946315) | Cod sursa (job #504908) | Cod sursa (job #1672163) | Cod sursa (job #314984) | Cod sursa (job #3145303)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define pb push_back
struct Point{double x; double y;};
bool comp_x(Point &A, Point &B){return A.x<B.x;}
bool comp_y(Point &A, Point &B){return A.y<B.y;}
double get_distance(Point A, Point B){
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
double bruteforce(vector<Point> points){
double minim = 4*1e18;
for(int i=0;i<=(int)points.size();i++) for(int j=i+1;j<=(int)points.size();j++){
minim=min(minim, get_distance(points[i],points[j]));
}
return minim;
}
double find_closest(vector<Point> &x_sorted, vector<Point> &y_sorted, int st, int dr){
if(dr-st+1<=3)
return bruteforce(y_sorted);
int mid=(st+dr)/2;
vector<Point> left_points;
vector<Point> right_points;
for(int i=st;i<=mid;i++)
left_points.push_back(x_sorted[i]);
for(int i=mid+1;i<=dr;i++)
right_points.push_back(x_sorted[i]);
double dist_left=find_closest(x_sorted, left_points, st, mid);
double dist_right=find_closest(x_sorted, right_points, mid+1, dr);
double dist=min(dist_left, dist_right);
vector<Point> strip;
for(int i=st;i<=dr;i++){
if(abs(y_sorted[i].x-x_sorted[mid].x)<=dist)
strip.push_back(y_sorted[i]);
}
for(int i=0;i<(int)strip.size();i++){
for(int j=i+1;j<(int)strip.size() && (strip[j].y-strip[i].y)<=dist;j++){
dist=min(dist,get_distance(strip[i],strip[j]));
}
}
return dist;
}
void solve(){
freopen("cmap.in", "r", stdin);
freopen("cmap.out", "w", stdout);
int N; cin>>N;
vector<Point> x_sorted;
vector<Point> y_sorted;
for(int i=0;i<N;i++){
double x, y; cin>>x>>y;
x_sorted.push_back({x,y});
y_sorted.push_back({x,y});
}
sort(x_sorted.begin(), x_sorted.end(), comp_x);
sort(y_sorted.begin(), y_sorted.end(), comp_y);
cout<<fixed<<setprecision(10)<<find_closest(x_sorted, y_sorted, 0, N-1);
}
int main()
{
ios_base::sync_with_stdio(false); cin.tie(0);
solve();
return 0;
}