UVA - 1615 Highway（高速公路）（贪心+区间选点）

题意：给定平面上n(n<=10)个点和一个值D，要求在x轴上选出尽量少的点，使得对于给定的每个点，都有一个选出的点离它的欧几里德距离不超过D。

分析：

1、根据D可以算出每个点在x轴上的可选区域，计算出区域的左右端点。

2、贪心选点，每次都选这个区域的最右端点，这样此端点可存在于尽可能多的区域。

#pragma comment(linker, "/STACK:102400000, 102400000")

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cctype>

#include<cmath>

#include<iostream>

#include<sstream>

#include<iterator>

#include<algorithm>

#include<string>

#include<vector>

#include<set>

#include<map>

#include<stack>

#include<deque>

#include<queue>

#include<list>

#define Min(a, b) ((a < b) ? a : b)

#define Max(a, b) ((a < b) ? b : a)

const double eps = 1e-;

inline int dcmp(double a, double b) {

    if(fabs(a - b) < eps)  return ;

    return a < b ? - : ;

}

typedef long long LL;

typedef unsigned long long ULL;

const int INT_INF = 0x3f3f3f3f;

const int INT_M_INF = 0x7f7f7f7f;

const LL LL_INF = 0x3f3f3f3f3f3f3f3f;

const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;

const int dr[] = {, , -, , -, -, , };

const int dc[] = {-, , , , -, , -, };

const int MOD = 1e9 + ;

const double pi = acos(-1.0);

const int MAXN =  + ;

const int MAXT =  + ;

using namespace std;

struct Node{

    double l, r;

    void set(double ll, double rr){

        l = ll;

        r = rr;

    }

    bool operator<(const Node& rhs)const{

        return r < rhs.r || (r == rhs.r && l < rhs.l);

    }

}num[MAXN];

int main(){

    int L, D;

    while(scanf("%d%d", &L, &D) == ){

        int n;

        scanf("%d", &n);

        for(int i = ; i < n; ++i){

            double x, y;

            scanf("%lf%lf", &x, &y);

            double len = sqrt(D * D - y * y);

            num[i].set(Max(x - len, 0.0), Min(x + len, L));

        }

        sort(num, num + n);

        int cnt = ;

        int pos = num[].r;

        for(int i = ; i < n; ++i){

            if(pos >= num[i].l && pos <= num[i].r) continue;

            pos = num[i].r;

            ++cnt;

        }

        printf("%d\n", cnt);

    }

    return ;

}