TOI14: plantation (Divide and Conquer)

#include <bits/stdc++.h>

using namespace std;
using pii = pair <int, int>;
using db = double;
const db INF = (db) 2e9;
vector <pii> point;

db distance(pii p1, pii p2){
    db dx = p1.first - p2.first;
    db dy = p1.second - p2.second;
    return sqrt(dx*dx + dy*dy);
}

db f(int l, int r){
    db mn = INF;
    for(int i=l;i<r;i++){
        for(int j=i+1;j<=r;j++){
            mn = min(mn, distance(point[i], point[j]));
        }
    }
    return mn;
}

db closest(int l, int r){
    if(r-l+1 <= 3) return f(l, r);
    int mid = (l+r)/2;
    db d = min(closest(l, mid), closest(mid+1, r));
    vector <pii> strip;
    for(int i=l;i<=r;i++){
        if(abs(point[mid].first - point[i].first) < d) strip.push_back({point[i].first, point[i].second});
        // คิดเฉพาะช่วงแกน x ที่น้อยกว่า
    }
    sort(strip.begin(), strip.end());
    int sz = strip.size();
    db mn = INF;
    for(int i=0;i<sz-1;i++){
        for(int j=i+1;j<sz;j++){
            if(strip[j].second - strip[i].second > d) break;
            // ไม่สนใจที่ระยะแกน y มากกว่า
            mn = min(mn, distance(strip[i], strip[j]));
        }
    }
    return min(d, mn);
}

int main(){

    int q;
    scanf("%d", &q);

    while(q--){
        int n;
        db d, r;
        scanf("%d%lf%lf", &n, &r, &d);
        for(int i=1;i<=n;i++){
            int x, y;
            scanf("%d%d", &x, &y);
            point.push_back({x, y});
        }
        sort(point.begin(), point.end());
        db dist = closest(0, n-1);
        if(dist - 2*r >= d) printf("Y");
        else printf("N");
        printf("\n");
        point.clear();
    }

    return 0;
}