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) {
      |                             ~~^~~~~~~~~~~~~~

#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) {
            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: TIME LIMIT EXCEEDED

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