首页 > 代码库 > 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 贪心
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。