学步园

PKU 1328 Radar Installation

http://acm.pku.edu.cn/JudgeOnline/problem?id=1328

我晕,太注意精度问题了让我WA了N次!!

注意我代码里给出的边界测试数据就OK了

贪心+排序:

#include <iostream><br /> #include <cmath><br /> #include <algorithm><br /> using namespace std;<br /> const double EPS = 1e-7;<br /> struct Point<br /> {<br /> double x;<br /> double y;<br /> double l;<br /> double r;<br /> bool operator < (const Point &t)const<br /> {<br /> return r < t.r;<br /> }<br /> };<br /> Point p[10002];<br /> bool used[10002];<br /> int main()<br /> {<br /> int i,j,k,m;<br /> int n;<br /> double d,t;<br /> int counter = 0;<br /> while (scanf("%d %lf",&n,&d)!=EOF)<br /> {<br /> if (n == 0 && d == 0)<br /> {<br /> break;<br /> }<br /> memset(used,0,sizeof(used));<br /> counter++;<br /> bool flag = 0;<br /> for (i=0;i<n;i++)<br /> {<br /> scanf("%lf %lf",&p[i].x,&p[i].y);<br /> t = sqrt(fabs(d*d - p[i].y*p[i].y));<br /> p[i].r = p[i].x + t;<br /> p[i].l = p[i].x - t;<br /> if ((fabs(p[i].y)>fabs(d)) || (d<0))<br /> {<br /> flag = 1;<br /> }<br /> }<br /> if (flag)<br /> {<br /> printf("Case %d: -1/n",counter);<br /> continue;<br /> }<br /> sort(p,p+n);<br /> int cnt = 0;<br /> for (i=0;i<n;i++)<br /> {<br /> if (!used[i])<br /> {<br /> cnt++;<br /> for (j=0;j<n;j++)<br /> {<br /> if (i!=j && !used[j])<br /> {<br /> if (p[j].l <= p[i].r && p[j].r >= p[i].r)<br /> // if ((p[i].r-p[j].l>=EPS) && (p[j].r-p[i].r >= EPS))<br /> {<br /> used[j] = 1;<br /> }<br /> }<br /> }<br /> used[i] = 1;<br /> }<br /> }<br /> printf("Case %d: %d/n",counter,cnt);<br /> }<br /> return 0;<br /> }<br /> /*<br /> 3 2<br /> 0 0<br /> 2 2<br /> 4 0</p> <p>*/