学步园

//贪心，注意贪心的方式，一开始我用从左往右对每一个点所对应的最右圆心坐标，接着逐步右移判断，看了POJ上的大牛讨论，知道这个<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>是错误的，于是进行了改正<br /> //正确的贪心算法应当是求出每个点它所满足的圆心范围，接着将问题转化为多区间选点问题。<br /> //即在N个闭区间上取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）<br /> #include<iostream><br /> #include<cmath><br /> using namespace std;<br /> struct coordinate//坐标结构体(x,y)<br /> {<br /> int x,y;<br /> }p[1001];<br /> struct interval//区间结构体[a,b]<br /> {<br /> double a;<br /> double b;<br /> }b[1001];<br /> int cmp_interval(const void *a,const void *b)<br /> {<br /> interval *A = (interval*) a;<br /> interval *B = (interval*) b;<br /> return (*A).b > (*B).b ? 1: -1;<br /> }//qsort的比较函数<br /> double search(coordinate a,int d)<br /> {<br /> double x;<br /> x = sqrt((double)(d*d - a.y*a.y)) + a.x;<br /> return x;<br /> }//找出所给坐标对应的圆心允许范围<br /> int main()<br /> {<br /> int n,d,c = 0,r;//r = number of radar,c = case<br /> bool impossible;<br /> while(cin >> n >> d)<br /> {<br /> if(n == 0)break;<br /> ++c;<br /> impossible = 0;<br /> r = 1;<br /> for(int i = 0;i < n;++i)<br /> {<br /> cin >> p[i].x >> p[i].y;<br /> if(abs(p[i].y) > d)<br /> impossible = 1;<br /> b[i].a = 2*p[i].x - search(p[i],d);<br /> b[i].b = search(p[i],d);<br /> }<br /> qsort(b,n,sizeof(b[0]),cmp_interval);//将区间按右边界从小到大排序<br /> if(impossible)<br /> cout <<"Case "<< c <<": " << -1 <<endl;<br /> else<br /> {<br /> int temp = 0;<br /> //贪心过程，策略是对包含区间取最右端的点，若左边界大于之前区间的右边界，则点数必须增加才能满足条件<br /> for(int i = 0;i < n;++i)<br /> {<br /> if(b[i].a > b[temp].b)<br /> {<br /> ++r;<br /> temp = i;<br /> }<br /> }<br /> cout <<"Case "<< c <<": " << r << endl;<br /> }<br /> }<br /> return 0;<br /> }