http://poj.org/problem?id=1328貪心。從左到右建立雷達(dá)，要盡量多地覆蓋島嶼。以島嶼的圓心d為半徑的圓與x軸有或者沒有交點(diǎn)。如果存在沒有交點(diǎn)的則不能實(shí)現(xiàn)！都存在交點(diǎn)的話，對(duì)于第i個(gè)島嶼計(jì)算出左右交點(diǎn)的x坐標(biāo)保存在a[i],b[i]里。對(duì)a[]排序，然后一次從左到右找雷達(dá)。初始right=b[1]為當(dāng)前最右邊的左標(biāo)，則對(duì)于下一個(gè)考慮島嶼i,如果a[i]>right則當(dāng)前需要建立的雷達(dá)不能覆蓋它，需要以此開始建立下一個(gè)雷達(dá);否則，如果b[i]<right，則需要更新right=b[i],考慮下一個(gè)島嶼。
別忘了最后需要建立雷達(dá)，即ans++:
#include<stdio.h>
double a[1003],b[1003];
int qsort(int s,int t)
{
int i,j;
double mid,tmp;
i=s;j=t;mid=a[(i+j)/2];
while (i<=j)
{
while (a[i]<mid) i++;
while (a[j]>mid) j--;
if (i<=j)
{
tmp=a[i];a[i]=a[j];a[j]=tmp;
tmp=b[i];b[i]=b[j];b[j]=tmp;
i++;
j--;
}
}
if (s<j) qsort(s,j);
if (i<t) qsort(i,t);
}
int main()
{
int n,i,x,y,d,ans,flag,t;
double right,xx;
scanf("%d%d",&n,&d);
t=0;
while (n!=0||d!=0)
{
flag=0;t++;
for (i=1;i<=n;i++)
{
scanf("%d%d",&x,&y);
if (y>d)
flag=1;
xx=sqrt(d*d-y*y);
a[i]=x-xx;b[i]=x+xx;
}
if (flag)
{
printf("Case %d: -1\n",t);
scanf("%d%d",&n,&d);
continue;
}
qsort(1,n);
ans=0;
right=b[1];i=2;
while (i<=n)
{
if (a[i]>right)
{
ans++;right=b[i];
}
if (b[i]<right)
right=b[i];
i++;
}
ans++;
printf("Case %d: %d\n",t,ans);
scanf("%d%d",&n,&d);
}
}
這個(gè)題，提交了無數(shù)次才ac，我嚓OLE！數(shù)據(jù)讀入需要注意啊，還有實(shí)型數(shù)要注意注意哦。