题意： 海上有一些岛屿（数目为n），需要在岸边（x 轴）修建一些雷达站覆盖这些岛屿，雷达的覆盖范围是d , 求最少需要多少雷达。
思路：求出每个岛屿能被雷达覆盖的，雷达可以放置的最左边和最右边位置，然后将每个岛屿按照左边的位置排序，放置雷达。
10955167NY_lv101328Accepted300K47MSC++1092B2012-10-25 18:45:07
View Code #include<iostream> #include<algorithm> #include<vector> #include<math.h> using namespace std; struct point{ int x,y; double l,r; }; vector<point> pt; int r,n; bool cmp(point p1,point p2) { return p1.l<p2.l; } int main() { int i,sum,cases=0; //double loc; point tmp; bool flags=false; while(cin>>n>>r&&n||r) { sum=0;flags=false;pt.clear(); for( i=0;i<n;i++) { cin>>tmp.x>>tmp.y; if(tmp.y>0) pt.push_back(tmp); if(tmp.y>r)flags=true; } if(flags||r<0) { cout<<"Case "<<++cases<<": -1"<<endl; continue; } for(i=0;i<pt.size();i++) { pt[i].l= pt[i].x- sqrt((double)r*r-pt[i].y*pt[i].y); pt[i].r= pt[i].x-pt[i].l+ pt[i].x; } sort(pt.begin(),pt.end(),cmp); i=0; while(i<pt.size()) { tmp=pt[i++]; sum++; while(i<pt.size()&&pt[i].l<=tmp.r&&tmp.l<=pt[i].l) //注意范围是不断的缩小的左右判断 { //tmp.l <=pt[i].l <= tmp.r tmp.l=pt[i].l; if(pt[i].r-tmp.r<1e-8) tmp.r=pt[i].r; i++; } } cout<<"Case "<<++cases<<": "<<sum<<endl; } return 0; }
转载于:https://www.cnblogs.com/lv-2012/archive/2012/10/25/2739950.html
相关资源：POJ1328-Radar Installation