หาระยะทางสั้นที่สุดระหว่างสองจุดใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา ระยะทางยกกำลังสองน้อยที่สุด (squared distance) ระหว่างจุดใดๆ สองจุดในชุดพิกัดที่กำหนด

ตัวอย่าง

coordinates = {{1, 2}, {1, 4}, {3, 5}}
Output: 4 (ระยะห่าง (1,2) และ (1,4) = (0)²+(2)² = 4)

อัลกอริทึม: Sweep Line + Balanced BST (Map)

เรียงจุดตาม x แล้ว sweep จากซ้ายไปขวา:

• รักษา map ytorightmostx: key=y, value=x สูงสุดที่เจอแล้วสำหรับ y นั้น
• สำหรับจุดใหม่ (px, py): หาจุดใน map ที่ y ใกล้ py (lower_bound py - sqrt(ret))
• ตรวจสอบจุดในช่วง y ที่เป็นไปได้ อัปเดต ret = min(ret, dist)
• Pruning: ถ้า x-distance² ≥ ret → ลบจุดนั้นออกจาก map (เพราะจุดถัดไป x จะไกลกว่า)

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

long long dist(long long xl, long long yl, long long xr, long long yr) {
    long long xd = xl - xr;
    long long yd = yl - yr;
    return xd * xd + yd * yd;
}

int solve(vector>& coordinates) {
    map ytorightmostx;
    sort(coordinates.begin(), coordinates.end());
    long long ret = 1e18;
    
    for (auto& p : coordinates) {
        auto it = ytorightmostx.lower_bound(p[1] - sqrt(ret));
        while (it != ytorightmostx.end()) {
            long long yd = it->first - p[1];
            if (yd > 0 && yd * yd >= ret) break;
            
            auto nxt = it; nxt++;
            ret = min(ret, dist(p[0], p[1], it->second, it->first));
            
            long long xd = it->second - p[0];
            if (xd * xd >= ret) {
                ytorightmostx.erase(it);
            }
            it = nxt;
        }
        ytorightmostx[p[1]] = p[0];
    }
    return ret;
}

int main() {
    vector> coord = {{1, 2}, {1, 4}, {3, 5}};
    cout << solve(coord) << endl;
    return 0;
}

ผลลัพธ์

4

คำอธิบายอัลกอริทึม

เป็นการปรับปรุงจาก Divide & Conquer (O(n log n)) ให้เป็น Sweep Line + Map (O(n log n) expected) โดยใช้ข้อเท็จจริงว่า points เรียงตาม x แล้ว จุดที่ x ระยะห่าง² ≥ best ไม่ต้องพิจารณาแล้ว

สรุป

Closest Pair of Points แบบ Sweep Line ใช้ map เก็บ y→max_x Pruning ด้วย current best distance หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ