CSES - Aalto Competitive Programming 2024 - wk10 - Wed - Results
Submission details
Task:Closest points
Sender:aalto2024k_004
Submission time:2024-11-13 16:53:16 +0200
Language:C++ (C++17)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'long long int bruteForce(std::vector<Point>&)':
input/code.cpp:45:14: error: 'LLONG_MAX' was not declared in this scope
   45 |     ll min = LLONG_MAX;
      |              ^~~~~~~~~
input/code.cpp:8:1: note: 'LLONG_MAX' is defined in header '<climits>'; did you forget to '#include <climits>'?
    7 | #include <iomanip>
  +++ |+#include <climits>
    8 | using namespace std;
input/code.cpp: In function 'double closest(std::vector<Point>&)':
input/code.cpp:96:5: error: 'sort' was not declared in this scope; did you mean 'sqrt'?
   96 |     sort(Px.begin(), Px.end(), compareX);
      |     ^~~~
      |     sqrt

Code

#include <float.h>
#include <math.h>
#include <stdlib.h>

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;

#define ll long long int

struct Point {
    ll x, y;
};

bool compareX(Point& p1, Point& p2) {
    return (p1.x != p2.x) ? (p1.x - p2.x) : (p1.y - p2.y);
}

bool compareY(Point& p1, Point& p2) {
    return (p1.y != p2.y) ? (p1.y - p2.y) : (p1.x - p2.x);
}

ll dist(Point& p1, Point& p2) {
    ll d = ((p1.x - p2.x) * (p1.x - p2.x)) +
           ((p1.y - p2.y) * (p1.y - p2.y));

    //cout << d << endl;
    return d;
}

ll stripClosest(vector<Point> strip, int size, ll d) {
    ll min = d;

    for (int i = 0; i < size; ++i)
        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min; ++j)
            if (dist(strip[i], strip[j]) < min)
                min = dist(strip[i], strip[j]);

    return min;
}

ll bruteForce(vector<Point>& P) {
    int n = P.size();
    ll min = LLONG_MAX;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (dist(P[i], P[j]) < min)
                min = dist(P[i], P[j]);
    return min;
}

ll closestUtil(vector<Point>& Px, vector<Point>& Py, int l, int r) {
    int n = r;

    if (n <= 3)
        return bruteForce(Px);

    int mid = n / 2;
   //cout << "mid -> " << mid << endl;
    Point midPoint = Px[l + mid];

    vector<Point> Pyl(mid);
    vector<Point> Pyr(n - mid);
    int li = 0, ri = 0;
    for (int i = 0; i < n; i++) {
        if ((Py[i].x < midPoint.x || (Py[i].x == midPoint.x && Py[i].y < midPoint.y)) && li < mid)
            Pyl[li++] = Py[i];
        else
            Pyr[ri++] = Py[i];
    }

    ll dl = closestUtil(Px, Pyl, l, mid);
    ll dr = closestUtil(Px, Pyr, l + mid, n - mid);

    ll d = min(dl, dr);

    vector<Point> strip(n);
    int j = 0;
    for (int i = 0; i < n; i++)
        if (abs(Py[i].x - midPoint.x) < d)
            strip[j] = Py[i], j++;

    return stripClosest(strip, j, d);
}

double closest(vector<Point>& P) {
    int n = P.size();
    vector<Point> Px(n);
    vector<Point> Py(n);
    for (int i = 0; i < n; i++) {
        Px[i] = P[i];
        Py[i] = P[i];
    }

    sort(Px.begin(), Px.end(), compareX);
    sort(Py.begin(), Py.end(), compareY);

    //cout << "hell" << endl;

    return closestUtil(Px, Py, 0, n);
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x;
        cin >> points[i].y;
    }

    cout << fixed << closest(points) << endl;
    return 0;
}