soj2075时间段贪心.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 60 行

#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

struct qujian
{
    double begin;
    double end;
};

bool cmp(qujian a,qujian b)
{
    if(a.begin<b.begin)
        return true;
    return false;
}

int main(void)
{
    int n;
    int num=1;
    qujian point[1000];
    int d;
    while(scanf("%d%d",&n,&d)&&(n||d))
    {
        int i;
        bool flag=true;
        for(i=0;i<n;i++)
        {
            int x,temp;
            scanf("%d%d",&x,&temp);
            if(temp>d)
                flag=false;
            point[i].begin=x-sqrt(d*d-temp*temp);
            point[i].end=x+sqrt(d*d-temp*temp);
        }
        if(!flag)
        {
            printf("Case %d: -1\n",num++);
            continue;
        }
        sort(point,point+n,cmp);
        int result=1;
        for (i=1;i<n;i++)
        {
            if(point[i].begin>point[i-1].end)
                result++;
            else if(point[i-1].end<point[i].end)
                point[i].end=point[i-1].end;
        }
        printf("Case %d: %d\n",num++,result);
    }
    return 0;
}