Geometry & Recognition

Brute-force : O(n^2),

Optimal: O(n log(n))

참고: people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf

참고: arxiv.org/pdf/1911.01973.pdf

//  points should be sorted in order of increasing x-component.
//
#define DIST2(p, q) ((p).x-(q).x)*((p).x-(q).x) + ((p).y-(q).y)*((p).y-(q).y)
// 수정: index range -> [left, right]; ClosestPair(points, 0, points.size()-1, closest);
int ClosestPair(std::vector<CPoint>& points, int left, int right, int closest[2]) {
    if (right - left >= 3) {
        int lpair[2], rpair[2], min_dist2;
        int mid = left + (right - left) / 2;                    // half index;
        int ldist = ClosestPair(points, left, mid, lpair);     // left side;
        int rdist = ClosestPair(points, mid+1, right, rpair); // right side;
        if (ldist < rdist) {
            closest[0] = lpair[0]; closest[1] = lpair[1];
            min_dist2 = ldist;
        } else {
            closest[0] = rpair[0]; closest[1] = rpair[1];
            min_dist2 = rdist;
        }
        // find points which lies near center strip(2d-strip);
        // Note our distance is the squar of actual distance;
        int width = int(sqrt(double(min_dist2))+ .5);
        int ll = left;
        while (points[ll].x < (points[mid].x - width - 1)) ll++;
        int rr = idx2;
        while (points[rr].x > (points[mid + 1].x + width + 1)) rr--;
        for (int i = ll; i < rr; i++) {
            for (int j = i + 1; j <= rr; j++) {
                int dist2 = DIST2(points[i], points[j]);
                if (min_dist2 > dist2) {
                    min_dist2 = dist2;
                    closest[0] = i; closest[1] = j;
                }
            }
        }
        return min_dist2;
    } 
    else if (right == left + 2) {
        return ClosestPair3(points, left, closest);
    }
    else if (right == left + 1) {
        closest[0] = left; closest[1] = right;
        return DIST2(points[left], points[right]);
    }
    else return INT_MAX;
};