Closest Pair of Points

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Point {
5
    long double x, y;
6
    int id; // unique index to break ties if needed
7
};
8
9
static inline long double sqr(long double v) { return v * v; }
10
static inline long double dist2(const Point& a, const Point& b) {
11
    return sqr(a.x - b.x) + sqr(a.y - b.y);
12
}
13
14
// Recursively compute closest pair on pts[l..r),
15
// maintaining that before the call the segment is sorted by x.
16
// On return, pts[l..r) will be sorted by y to enable linear merges up the recursion.
17
long double closest_pair_rec(int l, int r, vector<Point>& pts, vector<Point>& buf) {
18
    int n = r - l;
19
    if (n <= 40) {
20
        long double best = numeric_limits<long double>::infinity();
21
        for (int i = l; i < r; ++i) {
22
            for (int j = i + 1; j < r; ++j) {
23
                best = min(best, dist2(pts[i], pts[j]));
24
            }
25
        }
26
        // sort by y for parent merge
27
        sort(pts.begin() + l, pts.begin() + r, [](const Point& a, const Point& b){
28
            if (a.y != b.y) return a.y < b.y;
29
            if (a.x != b.x) return a.x < b.x;
30
            return a.id < b.id;
31
        });
32
        return best;
33
    }
34
35
    int m = l + n / 2;
36
    long double midx = pts[m].x; // median x before we reorder by y
37
38
    long double dl = closest_pair_rec(l, m, pts, buf);
39
    long double dr = closest_pair_rec(m, r, pts, buf);
40
    long double d = min(dl, dr);
41
42
    // Merge by y: pts[l..m) and pts[m..r) are y-sorted now; merge to buf, copy back.
43
    int i = l, j = m, k = 0;
44
    while (i < m && j < r) {
45
        if (pts[i].y < pts[j].y || (pts[i].y == pts[j].y && (pts[i].x < pts[j].x || (pts[i].x == pts[j].x && pts[i].id < pts[j].id))))
46
            buf[k++] = pts[i++];
47
        else
48
            buf[k++] = pts[j++];
49
    }
50
    while (i < m) buf[k++] = pts[i++];
51
    while (j < r) buf[k++] = pts[j++];
52
    for (int t = 0; t < k; ++t) pts[l + t] = buf[t];
53
54
    // Build the strip: points within distance d from the vertical line x = midx
55
    static const long double EPS = 1e-18L;
56
    vector<Point> strip;
57
    strip.reserve(n);
58
    for (int t = l; t < r; ++t) {
59
        if (fabsl(pts[t].x - midx) <= d + EPS) strip.push_back(pts[t]);
60
    }
61
62
    // Since pts[l..r) is y-sorted, 'strip' is also y-sorted.
63
    // Compare each point to the next few (<= 7) points.
64
    for (size_t a = 0; a < strip.size(); ++a) {
65
        // check following up to 7 points
66
        for (size_t b = a + 1; b < strip.size() && b <= a + 8; ++b) {
67
            // Early break on y difference if it already exceeds current d
68
            if (sqr(strip[b].y - strip[a].y) > d + EPS) break;
69
            d = min(d, dist2(strip[a], strip[b]));
70
        }
71
    }
72
73
    return d;
74
}
75
76
long double closest_pair(vector<Point> pts) {
77
    // Sort by x once before recursion. Use stable tie-breaking.
78
    sort(pts.begin(), pts.end(), [](const Point& a, const Point& b){
79
        if (a.x != b.x) return a.x < b.x;
80
        if (a.y != b.y) return a.y < b.y;
81
        return a.id < b.id;
82
    });
83
    vector<Point> buf(pts.size());
84
    long double best2 = closest_pair_rec(0, (int)pts.size(), pts, buf);
85
    return sqrt((double)best2);
86
}
87
88
int main() {
89
    ios::sync_with_stdio(false);
90
    cin.tie(nullptr);
91
92
    int n; 
93
    if (!(cin >> n)) return 0;
94
    vector<Point> pts(n);
95
    for (int i = 0; i < n; ++i) {
96
        long double x, y; cin >> x >> y;
97
        pts[i] = {x, y, i};
98
    }
99
100
    if (n < 2) { cout << 0 << "\n"; return 0; }
101
    // Optional early duplicate check could set answer to 0.
102
103
    cout.setf(std::ios::fixed); cout << setprecision(10) << closest_pair(pts) << "\n";
104
    return 0;
105
}
106

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Point { long double x, y; int id; };
5
static inline long double sqr(long double v){ return v*v; }
6
static inline long double dist2(const Point& a, const Point& b){ return sqr(a.x-b.x) + sqr(a.y-b.y); }
7
8
int main(){
9
    ios::sync_with_stdio(false);
10
    cin.tie(nullptr);
11
12
    int n; if(!(cin>>n)) return 0;
13
    vector<Point> p(n);
14
    for(int i=0;i<n;++i){ long double x,y; cin>>x>>y; p[i]={x,y,i}; }
15
    if(n<2){ cout<<0<<"\n"; return 0; }
16
17
    sort(p.begin(), p.end(), [](const Point& a, const Point& b){
18
        if(a.x!=b.x) return a.x<b.x;
19
        if(a.y!=b.y) return a.y<b.y;
20
        return a.id<b.id;
21
    });
22
23
    long double INF = numeric_limits<long double>::infinity();
24
    long double best2 = INF;
25
26
    // Active set ordered by y. Store (y, id) -> index in p for lookup.
27
    set<pair<long double,int>> active;
28
    int left = 0; // leftmost index still in 'active'
29
30
    for(int i=0;i<n;++i){
31
        Point cur = p[i];
32
        long double d = (best2==INF? INF : sqrt((double)best2));
33
34
        // Remove points whose x is too far from current point
35
        while(left<i){
36
            if (best2==INF) break; // nothing to remove yet
37
            if (cur.x - p[left].x > d) {
38
                active.erase({p[left].y, p[left].id});
39
                ++left;
40
            } else break;
41
        }
42
43
        // Query candidates within [y-d, y+d]
44
        long double ylow = cur.y - (best2==INF? INF : d);
45
        long double yhigh = cur.y + (best2==INF? INF : d);
46
        auto itlow = active.lower_bound({ylow, INT_MIN});
47
        auto ithigh = active.upper_bound({yhigh, INT_MAX});
48
49
        for(auto it = itlow; it != ithigh; ++it){
50
            const Point& q = p[ lower_bound(p.begin(), p.end(), it->second, [](const Point& a, int id){ return a.id < id; }) - p.begin() ];
51
            best2 = min(best2, dist2(cur, q));
52
        }
53
54
        active.insert({cur.y, cur.id});
55
    }
56
57
    cout.setf(std::ios::fixed); cout<<setprecision(10)<<sqrt((double)best2)<<"\n";
58
    return 0;
59
}
60

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Point { long double x, y; int id; };
5
static inline long double sqr(long double v){ return v*v; }
6
static inline long double dist2(const Point& a, const Point& b){ return sqr(a.x-b.x) + sqr(a.y-b.y); }
7
8
// Hash for pair<long long,long long>
9
struct PairHash {
10
    size_t operator()(const pair<long long,long long>& p) const noexcept {
11
        return std::hash<long long>()((p.first<<32) ^ (p.second + 0x9e3779b97f4a7c15ULL + (p.first<<6) + (p.first>>2)));
12
    }
13
};
14
15
pair<long long,long long> cellOf(const Point& a, long double cell) {
16
    // Use floor division to handle negatives correctly
17
    long double cx = floor(a.x / cell);
18
    long double cy = floor(a.y / cell);
19
    return { (long long)cx, (long long)cy };
20
}
21
22
int main(){
23
    ios::sync_with_stdio(false);
24
    cin.tie(nullptr);
25
26
    int n; if(!(cin>>n)) return 0;
27
    vector<Point> p(n);
28
    for(int i=0;i<n;++i){ long double x,y; cin>>x>>y; p[i]={x,y,i}; }
29
    if(n<2){ cout<<0<<"\n"; return 0; }
30
31
    // Randomize order to ensure expected guarantees
32
    mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
33
    shuffle(p.begin(), p.end(), rng);
34
35
    long double best2 = dist2(p[0], p[1]);
36
    if(best2 == 0) { cout<<0<<"\n"; return 0; }
37
38
    long double cell = max((long double)1e-18L, sqrt((double)best2)); // grid cell size ~ current best
39
40
    // Hash grid: map cell -> list of point indices already inserted
41
    unordered_map<pair<long long,long long>, vector<int>, PairHash> grid;
42
    auto rebuild = [&](int upto){
43
        grid.clear();
44
        for(int i=0;i<upto;++i){
45
            auto c = cellOf(p[i], cell);
46
            grid[c].push_back(i);
47
        }
48
    };
49
50
    // Insert first two points
51
    grid[cellOf(p[0], cell)].push_back(0);
52
    grid[cellOf(p[1], cell)].push_back(1);
53
54
    for(int i=2;i<n;++i){
55
        // If best improved sufficiently (cell too big), shrink cell and rebuild
56
        long double newCell = max((long double)1e-18L, sqrt((double)best2));
57
        if (newCell < cell * 0.5L) { cell = newCell; rebuild(i); }
58
59
        auto c = cellOf(p[i], cell);
60
        // Check neighbor cells in a 5x5 neighborhood (covers d-sized neighborhood when cell ~ d)
61
        for(long long dx=-2; dx<=2; ++dx){
62
            for(long long dy=-2; dy<=2; ++dy){
63
                auto it = grid.find({c.first+dx, c.second+dy});
64
                if(it==grid.end()) continue;
65
                for(int j : it->second){
66
                    best2 = min(best2, dist2(p[i], p[j]));
67
                    if(best2 == 0) { cout<<0<<"\n"; return 0; }
68
                }
69
            }
70
        }
71
        grid[c].push_back(i);
72
    }
73
74
    cout.setf(std::ios::fixed); cout<<setprecision(10)<<sqrt((double)best2)<<"\n";
75
    return 0;
76
}
77