qq_42468038
qq_42468038
采纳率100%
2018-06-15 11:24

poj 1328 Running time 错误 求助

5
已采纳

#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 的错误过不了,求助

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

4条回答

  • qq_42421714 resftlmuttmotw 3年前

    解题思路:
    首先可以明确的是:只要存在任意一个海岛位置超出雷达最大覆盖半径(即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有一个点),总放置点数不变
        ③ 重复这个过程直到所有区间被遍历完成
        !!!! 摘自他人博客
    
    点赞 评论 复制链接分享
  • qq_42421714 resftlmuttmotw 3年前
     #include <algorithm>
    #include <iostream>
    #include <cstdio>
    #include <cmath>
    using namespace std;
    struct node
    {
        double left,right; 
    }order[1005];
    bool compare(node a1,node a2)
    {
        return a1.left<=a2.left;
    }
    int main()
    {
        int island,r,q=0;
        while((cin>>island>>r)&&island&&r)
        {
            q++;
            const double R2=r*r;
            bool able=1;
            for(int i=1;i<=island;i++)
            {
                double x,y,delta;
                cin>>x>>y;
                delta=sqrt(R2-y*y);
                if(fabs(y)>r)
                    able=0;
                order[i].left=x-delta,order[i].right=x+delta;
            }
            int ans=1;
            if(able)
            {
                sort(order+1,order+1+island,compare);
                double RIGHT=order[1].right;
                for(int i=2;i<=island;i++)
                {
                    if(order[i].left>RIGHT)
                    {
                        ans++;
                        RIGHT=order[i].right;
                    }
                    else if(order[i].right<RIGHT)
                        RIGHT=order[i].right;
                }
            }
            else ans=-1;
            printf("Case %d: %d\n",q,ans);
        }
        return 0;
    }
    

    自己手打的,教了一下,没对
    思路应该没问题

    点赞 评论 复制链接分享
  • m0_37316071 m0_37316071 3年前

    for(int i=0;i {

    for(int i=0;i {

    for(int i=0;i

    有好多这个,应该有错吧

    点赞 评论 复制链接分享
  • caozhy 回答这么多问题就耍赖把我的积分一笔勾销了 3年前

为你推荐