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;
}