Closest points

input/code.cpp: In function 'long long int stripClosest(std::vector<Point>&, long long int)':
input/code.cpp:41:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for (int i = 0; i < strip.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~~
input/code.cpp:42:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < minDist && j - i <= 7; ++j) {
      |                             ~~^~~~~~~~~~~~~~

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
struct Point {
    long long x, y;
};
 
bool compareX(const Point& a, const Point& b) {
    return a.x < b.x;
}
 
bool compareY(const Point& a, const Point& b) {
    return a.y < b.y;
}
 
long long dist(const Point& a, const Point& b) {
    return (a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y);
}
 
long long bruteForce(const vector<Point>& points, long long left, long long right) {
    long long minDist = numeric_limits<long long>::max();
    for (int i = left; i < right; ++i) {
        for (int j = i + 1; j < right; ++j) {
            long long d = dist(points[i], points[j]);
            if (d < minDist) {
                minDist = d;
            }
        }
    }
    return minDist;
}
 
long long stripClosest(vector<Point>& strip, long long d) {
    long long minDist = d;
    sort(strip.begin(), strip.end(), compareY);
    for (int i = 0; i < strip.size(); ++i) {
        for (int j = i + 1; j < strip.size() && (strip[j].y - strip[i].y) < minDist && j - i <= 7; ++j) {
            long long d = dist(strip[i], strip[j]);
            if (d < minDist) {
                minDist = d;
            }
        }
    }
    return minDist;
}
 
long long closestUtil(vector<Point>& points, long long left, long long right) {
    if (right - left <= 3) {
        return bruteForce(points, left, right);
    }
 
    long long mid = left + (right - left) / 2;
    Point midPoint = points[mid];
 
    long long dl = closestUtil(points, left, mid);
    long long dr = closestUtil(points, mid, right);
 
    long long d = min(dl, dr);
 
    vector<Point> strip;
    for (int i = left; i < right; ++i) {
        if (abs(points[i].x - midPoint.x) < d) {
            strip.push_back(points[i]);
        }
    }
 
    return min(d, stripClosest(strip, d));
}
 
long long closest(vector<Point>& points, long long n) {
    return closestUtil(points, 0, n);
}
 
int main() {
    int n;
    cin >> n;
    if (n == 0) {
        cout << 0 << endl;
        return 0;
    }
    vector<Point> points(n);
 
    for (int i = 0; i < n; ++i) {
        cin >> points[i].x >> points[i].y;
    }
 
    sort(points.begin(), points.end(), compareX);
 
    cout << closest(points, n) << endl;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED