首页 > 代码库 > poj1328 贪心

poj1328 贪心

http://http://poj.org/problem?id=1328

神TM贪心。

不懂请自行搜博客。

AC代码:

#include<cstdio>#include<algorithm>#include<cstring>#include<cmath>using namespace std;struct Node{    double l;    double r;} node[2010],temp;int cmp(Node x,Node y){    return x.l<y.l;}int main(){    int n,num=0;    double d,a,b;    bool flag;    while( scanf("%d%lf",&n,&d)==2 && (n||d) )    {        flag=false;        for(int i=0; i<n; i++)        {            scanf("%lf%lf",&a,&b);            node[i].l=a-sqrt(d*d-b*b);            node[i].r=a+sqrt(d*d-b*b);            if(fabs(b)>d) flag=true;        }        if(flag==true) printf("Case %d: -1\n",++num);        else        {            sort(node,node+n,cmp);            temp=node[0];            int ans=1;            for(int i=1; i<n; i++)            {                if(node[i].l>temp.r)                {                    ans++;                    temp=node[i];                }                else if(node[i].r<temp.r)                    temp=node[i];            }            printf("Case %d: %d\n",++num,ans);        }    }    return 0;}

 

poj1328 贪心