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

Compiler report

In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from input/code.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h: In instantiation of 'constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare) [with _Tp = long long int; _Compare = long long int]':
input/code.cpp:20:19:   required from here
/usr/include/c++/11/bits/stl_algobase.h:281:17: error: '__comp' cannot be used as a function
  281 |       if (__comp(__b, __a))
      |           ~~~~~~^~~~~~~~~~

Code

#include <bits/stdc++.h>
using namespace std;

long long distance(pair<long long, long long> p1, pair<long long, long long> p2) {
    return (p1.first - p2.first)*(p1.first - p2.first) + (p1.second - p2.second)*(p1.second - p2.second);
}

bool comparison(pair<long long, long long> a, pair<long long, long long> b) {
    return a.second < b.second;
}

 
long long solve_rec(vector<pair<long long, long long>> &points, int begin, int end) {

    if (end - begin == 2) {
        return distance(points[begin], points[begin+1]);
    }

    else if (points.size() == 3) {
        return min(
            distance(points[begin], points[begin+1]),
            distance(points[begin+1], points[begin+2]),
            distance(points[begin], points[begin+2])
        );
    }
 
    long long N = (end - begin);
    long long M = begin + N / 2;

    long long left = solve_rec(points, begin, M);
    long long right = solve_rec(points, M, end);
 
    long long d = min(left, right);

    vector<pair<long long, long long>> around;
    
    for (int i = 0; i < N; i++) {
        if (abs(points[begin+i].first - points[M].first) < d) {
            around.push_back(points[begin+i]);
        }
    }

    sort(around.begin(), around.end(), comparison);

    int size = (int) around.size();

    for (int i = 0; i < size; ++i) {
        for (int j = i+1; j < size && (around[j].second - around[i].second) < d; j++) {
            long long dist = distance(around[i], around[j]);
            if (dist < d) 
                d = dist;
        }
    }
 
    return d; 

} 

float solve(vector<pair<long long, long long>> &points) { 
    return solve_rec(points, 0, points.size());
} 

int main() {

    int n;
    cin >> n;

    vector<pair<long long, long long>> points(n);
    for (int i = 0; i < n; i++)
        cin >> points[i].first >> points[i].second; 
    
    sort(points.begin(), points.end());

    cout << solve(points) << endl;

}