首页 > 代码库 > 贪心-poj1328
贪心-poj1328
http://poj.org/problem?id=1328
求出每个岛屿点在x轴上对应的区间(雷达在此区间内能探测到该岛屿).
将区间按照区间左端升序,然后贪心求出最小的相交区间个数.
坑:y^2爆int,爆long long.用double可过
#include <cstdio> #include <iostream> #include <algorithm> #include <cmath> using namespace std; struct haha{ double xz,xy; }a[1010]; bool operator <(haha aa,haha bb){ return aa.xy<bb.xy; } int main(){ int T,n,d; double x,y; double tmp; int flag=0; while(cin>>n>>d && n){ T++; flag=0; if(d<0)flag=-1; for(int i=0;i<n;i++){ cin>>x>>y; if(flag==0){ if(y>d || y<0){ flag=-1; }else{ tmp=sqrt(d*d-y*y); a[i].xz=(double)x-tmp; a[i].xy=(double)x+tmp; } } } sort(a,a+n); double xyy=a[0].xy; if(flag!=-1){ flag=1; for(int i=1;i<n;i++){ if(a[i].xz>xyy){ xyy=a[i].xy; flag++; } } } printf("Case %d: %d\n",T,flag); } return 0; }
贪心-poj1328
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。