Pagini recente » Cod sursa (job #975701) | Cod sursa (job #2205080) | Cod sursa (job #40857) | Cod sursa (job #802766) | Cod sursa (job #3154233)
#include <bits/stdc++.h>
#define mp make_pair
// #define int long long
using namespace std;
using db = double long;
const int NMAX = 1e5+2;
int n;
ifstream fin("cmap.in");
ofstream fout("cmap.out");
struct Point {
int x;
int y;
bool operator < (const Point &aux) const {
return mp(x, y) < mp(aux.x, aux.y);
}
};
db dist(Point a, Point b){
return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
db mindist(vector<Point> points, vector<Point> ysort){
int n = points.size();
if(n == 1){
return 1e18; // nu exista pereche
}
vector<Point> left = vector<Point>(points.begin(), points.begin()+n/2);
vector<Point> right = vector<Point>(points.begin()+n/2, points.end());
Point midpoint = left.back();
vector<Point> left_ysort, right_ysort;
for(auto it: ysort){
if(it < midpoint){
left_ysort.push_back(it);
}else{
right_ysort.push_back(it);
}
}
db ldist = mindist(left, left_ysort);
db rdist = mindist(right, right_ysort);
db ans = min(ldist, rdist);
vector<Point> cadran;
for(auto it: ysort){
db distx = (it.x - midpoint.x) * (it.x - midpoint.x);
if(distx < ans){
cadran.push_back(it);
}
}
n = cadran.size();
for(int i = 0; i < n; i++){
for(int j = i+1; j < n; j++){
ans = min(ans, dist(cadran[i], cadran[j]));
}
}
return ans;
}
signed main(){
fin >> n;
vector<Point> points(n), ysort(n);
for(auto &it: points){
fin >> it.x >> it.y;
}
ysort = points;
sort(points.begin(), points.end());
sort(ysort.begin(), ysort.end(), [](const Point &a, const Point &b){
return a.y < b.y;
});
fout << fixed << setprecision(10) << sqrtl(mindist(points, ysort));
return 0;
}