Pagini recente » Monitorul de evaluare | Cod sursa (job #3340405)
#include <bits/stdc++.h>
using namespace std;
#ifndef LOCAL
ifstream fin ("cmap.in");
ofstream fout ("cmap.out");
#define cin fin
#define cout fout
#endif
struct Vec2 {
double x, y;
Vec2(double _x = 0, double _y = 0) : x(_x), y(_y) {}
};
inline Vec2 operator+(Vec2 a, Vec2 b) {return Vec2(a.x + b.x, a.y + b.y);}
inline Vec2 operator-(Vec2 a, Vec2 b) {return Vec2(a.x - b.x, a.y - b.y);}
inline Vec2 operator*(Vec2 a, double b) {return Vec2(a.x * b, a.y * b);}
inline Vec2 operator/(Vec2 a, double b) {return Vec2(a.x / b, a.y / b);}
inline Vec2 &operator+=(Vec2 &a, Vec2 b) {return a = a + b;}
inline Vec2 &operator-=(Vec2 &a, Vec2 b) {return a = a - b;}
inline Vec2 &operator*=(Vec2 &a, double b) {return a = a * b;}
inline Vec2 &operator/=(Vec2 &a, double b) {return a = a / b;}
inline double abs(Vec2 v) {return sqrt(v.x * v.x + v.y * v.y);}
inline double cross(Vec2 a, Vec2 b) {return a.x * b.y - a.y * b.x;}
inline double dot(Vec2 a, Vec2 b) {return a.x * b.x + a.y * b.y;}
inline Vec2 norm(Vec2 v) {return v / abs(v);}
void read(Vec2 &v) {
cin>>v.x>>v.y;
}
const int BULAN = 7;
double sneakySolve(vector<Vec2> v) {
if(v.size() <= 1) {
return 1e15;
} else if(v.size() == 2) {
return abs(v[0] - v[1]);
} else if(v.size() == 3) {
return min(abs(v[0] - v[1]), min(abs(v[0] - v[2]), abs(v[1] - v[2])));
}
sort(v.begin(), v.end(), [](Vec2 a, Vec2 b){return a.x < b.x;});
int c1 = v.size() / 2;
double d = v[c1 - 1].x - 0.5;
vector<Vec2> sneaky1(v.begin(), v.begin() + c1);
vector<Vec2> sneaky2(v.begin() + c1, v.end());
double ans = min(sneakySolve(sneaky1), sneakySolve(sneaky2));
vector<Vec2> lst;
for(Vec2 i : v) {
if(abs(i.x - d) <= ans) {
lst.push_back(i);
}
}
sort(lst.begin(), lst.end(), [](Vec2 a, Vec2 b){return a.y < b.y;});
for(int i=0; i<lst.size(); ++i) {
for(int j=i+1; j<lst.size() && j <= i + BULAN; ++j) {
ans = min(ans, abs(lst[i] - lst[j]));
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n; cin>>n;
vector<Vec2> v(n);
for(int i=0; i<n; ++i) {
read(v[i]);
}
cout << fixed << setprecision(8) << sneakySolve(v);
return 0;
}