问一个关于区间选点的问题
建一个坐标系,x轴的上方是海洋,下方是陆地。海洋上散乱分布着一些岛屿,在岸上建立雷达站使得所有的岛都在监视范围内。第一行输入小岛的数目n和雷达的监视半径d。(当n=d=0时输入结束)
之后n行输入各个小岛的坐标。
求所需雷达的最小数目。
样例输入
3 2
1 2
-3 1
2 1
1 2
0 2
0 0
样例输出
Case 1: 2
Case 2: 1
#include <stdio.h>
#include <math.h>
int main()
{
int n,d,co=1;
while(scanf("%d%d",&n,&d),n&&d)
{
int i,j,flag=0,k;
float x[1002],y[1002];
for(i=0;i<n;i++)
{
scanf("%f%f",&x[i],&y[i]);
if(y[i]>d)
{
flag=1;
continue;
}
x[i]=x[i]-sqrt(d*d-y[i]*y[i]); //以每一个岛为圆心,d为半径,所画的圆与x轴的交点
y[i]=x[i]+sqrt(d*d-y[i]*y[i]);
}
if(flag)
{
printf("Case %d: -1\n",co);
break;
}
float x1,y1;
for(i=1;i<n;i++) //插入排序
{
x1=x[i];
y1=y[i];
for(j=0;j<i;j++)
if(y[i]<y[j])
break;
for(k=i-1;k>=j;k--)
{
x[k+1]=x[k];
y[k+1]=y[k];
}
x[j]=x1;
y[j]=y1;
}
float begin=x[n-1],last=y[n-1];
int num=1;
for(k=n-2;k>=0;k--) //在区间内找点,使得点最少,并且保证每个区间内最少有一个点
{
if(x[k]>=begin)
{
begin=x[k];
last=y[k];
continue;
}
if(begin>x[k]&&begin<=y[k])
{
last=y[k];
continue;
}
if(begin>y[k])
{
begin=x[k];
last=y[k];
num++;
}
}
printf("Case %d: %d\n",co,num);
co++;
}
return 0;
}
大哥帮忙看看为什么提交不上。。。