Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok

Cod sursa(job #3240635)

Utilizator pregoliStana Andrei pregoli 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;
}