| 196K | 0MS | C++ | 1352B |
先求出以每个island为圆心时，与x轴的交点，得到覆盖该island的雷达坐标的变化范围，然后从左向右，按贪心策略，求各个变化范围的最多交集（即若相邻几个island在x轴有交集，则在此处安装一个雷达），最后所求交集的个数即为minimal number of radar installations
#include<stdio.h>
#include<math.h>
int a[1000],b[1000];
int sort(int m,int n)
{
int start=m+1,end=n;
int temp;
while(1)
{
while(end!=m&&a[end]>=a[m])
end--;
while(a[start]<a[m]&&start<end)
start++;
if(end<=start)
{
temp=a[m];
a[m]=a[end];
a[end]=temp;
temp=b[m];
b[m]=b[end];
b[end]=temp;
return end;
}
else
{
temp=a[start];
a[start]=a[end];
a[end]=temp;
temp=b[start];
b[start]=b[end];
b[end]=temp;
}
}
}
void qsort(int m,int n)
{
if(m<n)
{
int q=sort(m,n);
qsort(m,q-1);
qsort(q+1,n);
}
}
int main()
{
int n,len,k;
double l[1000],r[1000];
scanf("%d %d",&n,&len);
int count=0;
while(n||len)
{
count++;
for(int i=0;i<n;i++)
scanf("%d %d",&a[i],&b[i]);
qsort(0,n-1);
double s=len*len;
for(k=0;k<n;k++)
{
if(b[k]>len||b[k]<0)
break;
double temp;
temp=sqrt(s-b[k]*b[k]);
l[k]=a[k]-temp;
r[k]=a[k]+temp;
}
if(k<n)
{
printf("Case %d: -1\n",count);
scanf("%d %d",&n,&len);
continue;
}
int min=1;
double t=r[0];
for(int j=1;j<n;j++)
{
if(t>=l[j])//若区域有交集，则继续向后移动
{
if(t>r[j])//注意该条件一定不能省略。
t=r[j];//更新区域范围
continue;
}
else
{
min++;//否则，须安装一个雷达，并在雷达的变化范围内最大限度地覆盖更多的island
t=r[j];
}
}
printf("Case %d: %d\n",count,min);
scanf("%d %d",&n,&len);
}
return 1;
}