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

Compiler report

input/code.cpp: In function 'long long int solve_rec(std::vector<std::pair<long long int, long long int> >&, int, int)':
input/code.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 0; i < around.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~~
input/code.cpp:43:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         for (int j = i+1; j < around.size() && (around[j].second - around[i].second) < d; j++) {
      |                           ~~^~~~~~~~~~~~~~~
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,...

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);
}
 
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(), [] (const auto& lhs, const auto& rhs) {
        return lhs.second < rhs.second;
    });

    for (int i = 0; i < around.size(); ++i) {
        for (int j = i+1; j < around.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;

}