poj 1328 Running time 错误 求助

Question

#include
using namespace std;
#include
void sort_com(int dot[][2],int num)//对小岛根据x坐标排序
{
int judge=1;
while(judge)
{
judge=0;
for(int i=0;i {
if(dot[i][0]>dot[i+1][0])
{
int temp1=dot[i][0];
int temp2=dot[i][1];
dot[i][0]=dot[i+1][0];
dot[i][1]=dot[i+1][1];
dot[i+1][0]=temp1;
dot[i+1][1]=temp2;
judge=1;
}
}
}
}
float range(int y,int d) //求一个岛在海岸线上所允许的圆心值范围，-1表示不存在
{
if(d*d-y*y return -1;
return sqrt((float)(d*d-y*y));
}
int select_dot(int dot[][2],int d,int num)//寻找区间最少数
{
int b[100][2];
for(int i=0;i {
float delt=range(dot[i][1],d);
if(delt return -1;
b[i][0]=dot[i][0]-delt;
b[i][1]=dot[i][0]+delt;
}
int center=b[0][1];
int result=1;
for(int i=0;i {
if(b[i][0]>center)
{
center=b[i][1];
result++;//需要增加一个雷达
}
}
return result;
}
int main(void)
{
int dot[100][2],d,num,times=0;//times表示有几个case
int answer[100];
for(int i=0;i for(int j=0;j dot[i][j]=0;
cin>>num>>d;
while(d!=0||num!=0)
{
for(int i=0;i cin>>dot[i][0]>>dot[i][1];
sort_com(dot,num);
answer[times]=select_dot(dot,d,num);
times++;
cin>>num>>d;
}
for(int i=1;i<=times;i++)
cout<<"Case "<<i<<": "<<answer[i-1]<<endl;//输出
return 0;
}
poj 显示Running time 的错误过不了，求助

Answer 1

解题思路：
首先可以明确的是：只要存在任意一个海岛位置超出雷达最大覆盖半径（即y>d），则无解.
在所有海岛的 y<=d 的前提下去思考此问题，
那么此问题的切入点是需要知道【一个雷达要覆盖一个海岛，其可以安装范围是多少】
以海岛坐标(x,y)为圆心，用雷达覆盖半径d画圆，根据前提条件可知，
这个圆与x轴必定存在最少1个(y=d)、最多2个交点(y<d).
可以认为1个交点是2个交点重合的特殊情况，那么这2个交点在x轴上构成的线性区间，
可以看作海岛的被覆盖范围在x轴上的投影 (由此就可以把二维的几何问题转化成一维几何问题)
按照所有海岛的x轴坐标，从小到大依次计算每个海岛在x轴上的投影区间（投影可能存在重叠），
同时把每个雷达抽象成1个点，那么此问题就转化成：
【已知x轴上若干个区间（可能存在交集），现在要往这些区间内放若干个点，
问怎样放置这些点，使得每个区间内至少存在一个点，且所放置的点的总量尽可能最少】

  可使用贪心算法求解：
    根据每个区间的左端点坐标对所有区间从左到右排序:
    ① 在左起第一个区间A 的右端点 A.R 放置一个点，总放置点数 P+1 
    ② 若下一个区间B 的左端点 B.L > A.R, 
        说明 区间A 与 区间B 无交集，此时在区间B 的右端点 B.R 放置一个点，总放置点数 P+1 
       否则说明 区间A 与 区间B 相交, 此时进一步判断，若 B.R < A.R，
        说明 区间B 在 区间A 的内部，此时把原本放置在 A.R 的点移动到 B.R（确保区间B有一个点），总放置点数不变
    ③ 重复这个过程直到所有区间被遍历完成
    !!!! 摘自他人博客