Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cstdio>
- #include <cstddef>
- #include <ctime>
- #include <vector>
- #include <algorithm>
- #include <bits/ios_base.h>
- #include <iostream>
- #include <random>
- #define DEBUG
- #ifdef DEBUG
- #define eprintf(...) fprintf(stderr, __VA_ARGS__)
- #else
- #define eprintf(...)
- #endif
- using namespace std;
- const long long INF = 8e18 + 1;
- struct Point {
- long long x;
- long long y;
- };
- struct Res {
- Point a;
- Point b;
- long long d = INF;
- };
- long long dist(const Point &first, const Point &second) {
- return (first.x - second.x) * (first.x - second.x) +
- (first.y - second.y) * (first.y - second.y);
- }
- vector<Point>
- strip(const Point &p, long long d, const vector<Point> &points, int left,
- int right) {
- vector<Point> res;
- for (int i = left; i < right; i++) {
- long long cur_d = (p.x - points[i].x) * (p.x - points[i].x);
- if (cur_d < d) {
- res.push_back(points[i]);
- }
- }
- return res;
- }
- void closest(const vector<Point> &points, Res &res) {
- long long min_dist = res.d;
- int a = -1, b = -1;
- for (int i = 0; i < points.size(); i++) {
- for (int j = i + 1; j < points.size()
- && (points[i].y - points[j].y) *
- (points[i].y - points[j].y) <
- min_dist; j++) {
- long long cur_dist = dist(points[i], points[j]);
- if (cur_dist < min_dist) {
- min_dist = cur_dist;
- a = i;
- b = j;
- }
- }
- }
- if (a != -1 && b != -1) {
- res.a = points[a];
- res.b = points[b];
- res.d = min_dist;
- }
- }
- Res brute_force(const vector<Point> &points, int left, int right) {
- Res res = Res();
- for (int i = left; i < right; i++) {
- for (int j = i + 1; j < right; j++) {
- long long d = dist(points[i], points[j]);
- if (res.d > d) {
- res.d = d;
- res.a = points[i];
- res.b = points[j];
- }
- }
- }
- return res;
- }
- Res divide_and_conquer(const vector<Point> &points, int left, int right) {
- if (right - left <= 3) {
- return brute_force(points, left, right);
- }
- int m = (left + right) / 2;
- Res left_res = divide_and_conquer(points, left, m);
- Res right_res = divide_and_conquer(points, m, right);
- long long d = min(left_res.d, right_res.d);
- auto strip_points = strip(points[m], d, points, left, right);
- sort(strip_points.begin(), strip_points.end(),
- [](const Point &a, const Point &b) -> bool {
- return a.y > b.y;
- });
- Res res = left_res.d < right_res.d ? left_res : right_res;
- closest(strip_points, res);
- return res;
- }
- void stress_test() {
- std::random_device rd;
- std::mt19937_64 gen(rd());
- std::uniform_int_distribution<long long> dis;
- while (true) {
- int n = abs(rand() % 50000) + 2;
- vector<Point> points;
- for (int i = 0; i < n; i++) {
- long long x = dis(gen) % 1000000000;
- long long y = dis(gen) % 1000000000;
- points.push_back({x, y});
- }
- sort(points.begin(), points.end(),
- [](const Point &a, const Point &b) -> bool {
- return a.x > b.x;
- });
- Res expected = brute_force(points, 0, n);
- Res actual = divide_and_conquer(points, 0, n);
- if (expected.d != actual.d) {
- eprintf("Got wrong res:\nexpected: %d %d, %d %d, %d\nactual: %d %d, %d %d, %d\n",
- (int) expected.a.x, (int) expected.a.y, (int) expected.b.x,
- (int) expected.b.y, (int) expected.d,
- (int) actual.a.x, (int) actual.a.y, (int) actual.b.x,
- (int) actual.b.y, (int) actual.d);
- eprintf("%d\n", n);
- for (auto &point : points) {
- eprintf("%d %d\n", (int) point.x, (int) point.y);
- }
- return;
- } else {
- eprintf("ok %d\n", n);
- }
- }
- }
- int main() {
- ios_base::sync_with_stdio(false);
- cin.tie(0);
- vector<Point> points;
- //stress_test();
- int n;
- cin >> n;
- for (int i = 0; i < n; i++) {
- long long x, y;
- cin >> x >> y;
- points.push_back({x, y});
- }
- sort(points.begin(), points.end(),
- [](const Point &a, const Point &b) -> bool {
- return a.x > b.x;
- });
- auto res = divide_and_conquer(points, 0, n);
- //auto res = brute_force(points, 0, n);
- cout << res.a.x << " " << res.a.y << " " << res.b.x << " " << res.b.y;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement