| Task: | Closest points |
| Sender: | aalto26jw_003 |
| Submission time: | 2026-11-11 16:33:23 +0200 |
| Language: | C++ (C++20) |
| Status: | READY |
| Result: | ACCEPTED |
| test | verdict | time | |
|---|---|---|---|
| #1 | ACCEPTED | 0.00 s | details |
| #2 | ACCEPTED | 0.13 s | details |
| #3 | ACCEPTED | 0.10 s | details |
| #4 | ACCEPTED | 0.13 s | details |
| #5 | ACCEPTED | 0.00 s | details |
| #6 | ACCEPTED | 0.15 s | details |
| #7 | ACCEPTED | 0.00 s | details |
| #8 | ACCEPTED | 0.00 s | details |
| #9 | ACCEPTED | 0.00 s | details |
| #10 | ACCEPTED | 0.06 s | details |
| #11 | ACCEPTED | 0.00 s | details |
| #12 | ACCEPTED | 0.00 s | details |
| #13 | ACCEPTED | 0.06 s | details |
| #14 | ACCEPTED | 0.00 s | details |
| #15 | ACCEPTED | 0.00 s | details |
| #16 | ACCEPTED | 0.15 s | details |
| #17 | ACCEPTED | 0.06 s | details |
| #18 | ACCEPTED | 0.00 s | details |
Code
// FULL TEMPLATE: delete every block you don't use. Blocks don't depend on each other.
// Nodes are 1..n (slot 0 unused) like the Python samples. Arrays are 0-indexed.
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
const ll MOD = 1'000'000'007;
const ll INF = LLONG_MAX / 4; // INF + INF still fits in ll
struct P {
ll x, y;
P operator-(P o) const { return {x - o.x, y - o.y}; }
bool operator<(P o) const { return tie(x, y) < tie(o.x, o.y); }
bool operator==(P o) const { return x == o.x && y == o.y; }
bool operator!=(P o) const { return !(*this == o); }
};
ll dot(P a, P b) { return a.x * b.x + a.y * b.y; }
ll dist2(P a, P b) { return dot(a - b, a - b); } // squared distance, compare these instead of sqrt
P read_p() {
P p;
cin >> p.x >> p.y;
return p;
}
vector<P> read_pts(int n) {
vector<P> v(n);
for (auto &p : v)
p = read_p();
return v;
}
ll isqrt_ll(ll v) { // floor(sqrt(v)), exact
ll r = sqrtl((long double)v);
while (r * r > v)
r--;
while ((r + 1) * (r + 1) <= v)
r++;
return r;
}
ll closest_pair(vector<P> pts) { // (30.2) min squared distance, sweep by x, active set sorted by y
sort(all(pts));
ll best = dist2(pts[0], pts[1]);
set<pair<ll, ll>> active; // (y, x) of points with x in [cur.x - d, cur.x]
int j = 0;
for (P p : pts) {
ll d = isqrt_ll(best); // a closer point has |dx| <= d and |dy| <= d
while (p.x - pts[j].x > d)
active.erase({pts[j].y, pts[j].x}), j++;
for (auto it = active.lower_bound({p.y - d, LLONG_MIN}); it != active.end() && it->first <= p.y + d; ++it)
best = min(best, dist2(p, {it->second, it->first}));
active.insert({p.y, p.x});
}
return best;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
int n;
cin >> n;
cout << closest_pair(read_pts(n)) << '\n';
}
Test details
Test 1
Verdict: ACCEPTED
| input |
|---|
| 100 58 36 81 -7 46 49 87 -58 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 2
Verdict: ACCEPTED
| input |
|---|
| 200000 -222 -705 277 680 -436 561 528 -516 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 3
Verdict: ACCEPTED
| input |
|---|
| 200000 -464738043 865360844 465231470 129093134 -276549869 -21946314 111055008 -48821736 ... |
| correct output |
|---|
| 25413170 |
| user output |
|---|
| 25413170 |
Test 4
Verdict: ACCEPTED
| input |
|---|
| 200000 1 513001000 2 689002000 3 785003000 4 799004000 ... |
| correct output |
|---|
| 1000000 |
| user output |
|---|
| 1000000 |
Test 5
Verdict: ACCEPTED
| input |
|---|
| 4 0 0 0 3 3 0 1 1 |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 6
Verdict: ACCEPTED
| input |
|---|
| 200000 1 0 1 1 1 2 1 3 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 7
Verdict: ACCEPTED
| input |
|---|
| 4 1 2 10 3 3 5 8 5 |
| correct output |
|---|
| 8 |
| user output |
|---|
| 8 |
Test 8
Verdict: ACCEPTED
| input |
|---|
| 4 10 6 4 10 8 3 2 3 |
| correct output |
|---|
| 13 |
| user output |
|---|
| 13 |
Test 9
Verdict: ACCEPTED
| input |
|---|
| 2 -999999999 -999999999 999999999 999999999 |
| correct output |
|---|
| 7999999984000000008 |
| user output |
|---|
| 7999999984000000008 |
Test 10
Verdict: ACCEPTED
| input |
|---|
| 200000 0 1 1 1 2 1 3 1 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 11
Verdict: ACCEPTED
| input |
|---|
| 8 1 10000 -1 -10000 2 0 -2 0 ... |
| correct output |
|---|
| 16 |
| user output |
|---|
| 16 |
Test 12
Verdict: ACCEPTED
| input |
|---|
| 3 -1000000000 -1000000000 1000000000 1000000000 0 0 |
| correct output |
|---|
| 2000000000000000000 |
| user output |
|---|
| 2000000000000000000 |
Test 13
Verdict: ACCEPTED
| input |
|---|
| 199999 1 1 2 1 3 1 4 1 ... |
| correct output |
|---|
| 1 |
| user output |
|---|
| 1 |
Test 14
Verdict: ACCEPTED
| input |
|---|
| 4 0 0 5 8 6 1 10000 0 |
| correct output |
|---|
| 37 |
| user output |
|---|
| 37 |
Test 15
Verdict: ACCEPTED
| input |
|---|
| 435 -842 -199 -480 798 -176 -406 792 608 ... |
| correct output |
|---|
| 2 |
| user output |
|---|
| 2 |
Test 16
Verdict: ACCEPTED
| input |
|---|
| 200000 1 0 1 2 1 4 1 6 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 17
Verdict: ACCEPTED
| input |
|---|
| 200000 0 1 2 1 4 1 6 1 ... |
| correct output |
|---|
| 4 |
| user output |
|---|
| 4 |
Test 18
Verdict: ACCEPTED
| input |
|---|
| 3 -1000000000 -1000000000 1000000000 1000000000 1000000000 -1000000000 |
| correct output |
|---|
| 4000000000000000000 |
| user output |
|---|
| 4000000000000000000 |
