TOI14: plantation (Line Sweep)

#include <bits/stdc++.h>

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

db Distance(int x1, int y1, int x2, int y2){
    db dx = abs(x1 - x2) * 1.0;
    db dy = abs(y1 - y2) * 1.0;
    return (db) sqrt( dx * dx + dy * dy );
}

int Index(int x, int l, int r, vector <int> &coor, int mn = INF){
    while(l <= r){
        int mid = (l + r) / 2;
        if(coor[mid] >= x)
            r = mid - 1, mn = min(mn, mid);
        else
            l = mid + 1;
    }
    return mn;
}

void Solve(){

    int n; scanf("%d", &n);
    db r, d; scanf("%lf%lf", &r, &d);

    pi XY[n + 10];
    vector <int> coor;
    for(int i=1;i<=n;i++){
        int x, y;
        scanf("%d%d", &x, &y);
        XY[i] = {x, y};
        coor.push_back(x);
    }

    sort(XY + 1, XY + n + 1);
    sort(coor.begin(), coor.end());
    coor.resize( unique(coor.begin(), coor.end()) - coor.begin() );
    int sz_coor = coor.size();

    vector <int> event[sz_coor + 10];
    for(int i=1;i<=n;i++){
        int x = XY[i].first, y = XY[i].second;
        int idx = Index(x, 0, sz_coor - 1, coor);
        event[idx].push_back(y);
    }

    db closest = INF;

    int sz_cur = 0, sz_pre = 0;
    for(int i=0;i<sz_coor;i++){
        sz_cur = event[i].size();
        for(int j=0;j<sz_cur;j++){
            if(j > 0) closest = min(closest, (db) (event[i][j] - event[i][j-1]) );
            if(i == 0) continue;
            int idx_pre = Index(coor[i] - closest, 0, i - 1, coor);
            if(idx_pre == INF) continue;
            for(int k=idx_pre;k<i;k++){
                {
                    int mn = INF, l = 0, r = sz_pre - 1;
                    while(l <= r){
                        int mid = (l + r) / 2;
                        if(event[k][mid] >= event[i][j])
                            r = mid - 1, mn = min(mn, mid);
                        else
                            l = mid + 1;
                    }
                    if(mn != INF) closest = min(closest, Distance(coor[k], event[k][mn], coor[i], event[i][j]) );
                }
                {
                    int mx = -INF, l = 0, r = sz_pre - 1;
                    while(l <= r){
                        int mid = (l + r) / 2;
                        if(event[k][mid] <= event[i][j])
                            l = mid + 1, mx = max(mx, mid);
                        else
                            r = mid - 1;
                    }
                    if(mx != -INF) closest = min(closest, Distance(coor[k], event[k][mx], coor[i], event[i][j]));
                }
            }
        }
        sz_pre = sz_cur;
    }

    if(closest - 2.0 * r >= d) printf("Y");
    else printf("N");
}

int main(){

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

    while(Q --){
        Solve();
        printf("\n");
    }

    return 0;
}