UVA - 1615 Highway 區間覆蓋

UVA - 1615 Highway 區間覆蓋

題目大意：在平面上有n個點和一個值D，要求再長度為L的x軸上選出盡量少的點，使得對於給定的每個點，都有一個選出的點離它的歐幾裡德距離不超過D

解題思路：算出每個點的區間范圍。區間的重疊部分由幾個區間構成就有幾個點滿足要求。

#include
#include
#include
#define maxn 100010
using namespace std;
double L, D;
int n;
struct villages{
    double l, r;
}vill[maxn];

bool cmp(const villages a, const villages b) {
    if(a.r == b.r)
        return a.l < b.l;
    else
        return a.r < b.r;
}

int main() {
    while(scanf("%lf%lf", &L, &D) == 2) {
        scanf("%d", &n);
        double x, y, len;
        for(int i = 0; i < n; i++) {
            scanf("%lf%lf", &x, &y);
            len = sqrt(D * D - y * y);
            vill[i].l = max(x - len,0.0);
            vill[i].r = min(L,x + len); 
        }
        sort(vill, vill + n, cmp);
        int ans = 1;
        double r = vill[0].r;
        for(int i = 1; i < n; i++)
            if(r >= vill[i].l && r <= vill[i].r) 
                continue;
            else{
                ans++;
                r = vill[i].r;
            }
        printf("%d\n", ans);
    }
    return 0;
}