Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok
Cod sursa(job #3240635)
Utilizator | Data | 18 august 2024 23:08:51 | |
---|---|---|---|
Problema | Cele mai apropiate puncte din plan | Scor | 75 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 2.41 kb |
#include <bits/stdc++.h>
using namespace std;
const string FILE_NAME = "cmap.";
ifstream fin(FILE_NAME + "in");
ofstream fout(FILE_NAME + "out");
constexpr unsigned PRECISION = 6;
inline int64_t to2(int x) {
return 1LL * x * x;
}
struct Point {
int x, y;
bool operator < (const Point &other) const noexcept {
return make_pair(x, y) < make_pair(other.x, other.y);
}
int64_t sqrDistTo(const Point &other) const {
return to2(x - other.x) + to2(y - other.y);
}
};
istream& operator >> (istream &in, Point &p) {
in >> p.x >> p.y;
return in;
}
vector<Point> readPoints() {
int n;
fin >> n;
vector<Point> points(n);
for (auto &p : points) {
fin >> p;
}
return points;
}
int64_t sqrSmallestDist(const vector<Point> &points, const vector<Point> &ySortedPoints) {
const int n = points.size();
if (n < 2) {
return numeric_limits<int64_t>::max();
}
const vector<Point>::const_iterator midPointIt = points.begin() + n/2;
auto le = vector<Point>(points.begin(), midPointIt);
auto ri = vector<Point>(midPointIt, points.end());
vector<Point> leSortedByY, riSortedByY;
for (const auto &point : points) {
if (point < *midPointIt) {
leSortedByY.push_back(point);
} else {
riSortedByY.push_back(point);
}
}
int64_t ansLe = sqrSmallestDist(le, leSortedByY);
int64_t ansRi = sqrSmallestDist(ri, riSortedByY);
int64_t ans = min(ansLe, ansRi);
vector<Point> nearStripePoints;
for (const auto &point : ySortedPoints) {
if (to2(point.x - midPointIt->x) < ans) {
nearStripePoints.push_back(point);
}
}
for (size_t i = 0; i < nearStripePoints.size(); i++) {
for (size_t j = i + 1; j < nearStripePoints.size(); j++) {
ans = min(ans, nearStripePoints[i].sqrDistTo(nearStripePoints[j]));
}
}
return ans;
}
int main() {
auto points = readPoints();
sort(points.begin(), points.end());
auto ySortedPoints = points;
sort(ySortedPoints.begin(), ySortedPoints.end(), [](const auto &fi, const auto &se)->bool {
return fi.y < se.y;
});
const double ans = sqrt(sqrSmallestDist(points, ySortedPoints));
fout << fixed << setprecision(PRECISION) << ans << endl;
fout.close();
return 0;
}