雷达覆盖，贪心，类似活动安排(POJ1328)

题目链接：http://poj.org/problem?id=1328

解题报告：

1、按照头结点排序。

#include <cstdio>

#include <cmath>

#include <string.h>

#include <algorithm>

using namespace std;

struct point

{

    double x;

    double y;

} dis[],pos[];

bool cmp(const point a,const point b)

{

    return a.x<b.x;

}

int n;

double d;

int main()

{

    int Case=;

    while(scanf("%d%lf",&n,&d),n!=||d!=)

    {

        memset(dis,,sizeof(dis));

        bool flag=true;

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

        {

            scanf("%lf%lf",&dis[i].x,&dis[i].y);

            if(d<fabs(dis[i].y))

            {

                flag=false;

            }

        }

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

        {

            pos[i].x=dis[i].x-sqrt(d*d*1.0-dis[i].y*dis[i].y);///计算一下左右区间

            pos[i].y=dis[i].x*1.0+sqrt(d*d*1.0-dis[i].y*dis[i].y);

        }

        if(flag)

        {

            sort(pos,pos+n,cmp);

            point tmp=pos[];

            int ans=;

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

            {

                if(pos[i].x>tmp.y)//没有重合的地方

                {

                    ans++;

                    tmp=pos[i];

                }

                else if(pos[i].y<tmp.y)///有重合的地方且下一个岛屿的右覆盖较远

                    tmp=pos[i];

            }

            printf("Case %d: %d\n",++Case,ans);

        }

        else printf("Case %d: %d\n",++Case,-);

    }

    return ;

}

2、按照尾节点排序。

#include <cstdio>

#include <cmath>

#include <string.h>

#include <algorithm>

using namespace std;

struct point

{

    double x;

    double y;

} dis[],pos[];

bool cmp(const point a,const point b)

{

    return a.y<b.y;///按尾节点排序

}

int n;

double d;

int main()

{

    int Case=;

    while(scanf("%d%lf",&n,&d),n!=||d!=)

    {

        memset(dis,,sizeof(dis));

        bool flag=true;

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

        {

            scanf("%lf%lf",&dis[i].x,&dis[i].y);

            if(d<fabs(dis[i].y))

            {

                flag=false;

            }

        }

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

        {

            pos[i].x=dis[i].x-sqrt(d*d*1.0-dis[i].y*dis[i].y);

            pos[i].y=dis[i].x*1.0+sqrt(d*d*1.0-dis[i].y*dis[i].y);

        }

        if(flag)

        {

            sort(pos,pos+n,cmp);

            point tmp=pos[];

            int ans=;

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

            {

                if(pos[i].x>tmp.y)///没有重复

                {

                    ans++;

                    tmp=pos[i];

                }

                else if(pos[i].x>tmp.y)

                    tmp=pos[i];

            }

            printf("Case %d: %d\n",++Case,ans);

        }

        else printf("Case %d: %d\n",++Case,-);

    }

    return ;

}