Hey__Juude 2017-05-24 17:02 采纳率: 100%
浏览 1360
已采纳

poj 1328贪心算法,一直WA

根据网上的思路写了下代码,测试了几个用例都没问题,哪个大神帮忙看下哪里有问题啊。。。

题意:假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧,而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上,只能覆盖d距离,所以如果小岛能够被覆盖到的话,它们之间的距离最多为d。

题目要求计算出能够覆盖给出的所有岛屿的最少雷达数目

 #include<iostream>
#include<queue>
#include<math.h>
#include<algorithm>
using namespace std;

struct dot
{
    int x;
    int y;
}abc[10000];

float left(dot a,int r)
{
    return a.x - sqrt(r*r*1.0 - a.y*a.y*1.0);
}

float right(dot a, int r)
{
    return a.x + sqrt(r*r*1.0 - a.y*a.y*1.0);
}

int comp(const void* a, const void* b)
{
    int aa = (*(dot*)a).x;
    int bb = (*(dot*)b).x;
    return aa - bb;
}


int main()
{
    int num, r;
    cin >> num >> r;
    bool flag = false;
    int count = 0;
    int ans[1000];
    memset(ans, 0, sizeof(ans));
    while (num != 0 && r != 0)
    {
        count++;
        int cir = 0;
        for (int i = 0; i < num; i++)
        {
            dot temp;
            cin >> temp.x >> temp.y;
            if (temp.y > r||temp.y<0)
                flag = true;
            abc[i] = temp;
        }
        if (flag)
        {
            ans[count] = -1;
            cout << "Case " << count << ": " << -1 << endl;
        }
        else
        {
            qsort(abc, num, sizeof(abc[0]), comp);
            dot temp = abc[0];
            cir++;
            float now = right(temp, r);
            for (int i = 1; i < num; i++)
            {
                temp = abc[i];
                if (now >= left(temp, r))
                    continue;
                else
                {
                    now = right(temp, r);
                    cir++;
                }
            }
            ans[count] = cir;
            cout << "Case " << count << ": " << cir << endl;
        }

        cin >> num >> r;
    }

    return 0;

}
  • 写回答

1条回答 默认 最新

  • threenewbee 2017-05-25 00:13
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 c程序不知道为什么得不到结果
  • ¥40 复杂的限制性的商函数处理
  • ¥15 程序不包含适用于入口点的静态Main方法
  • ¥15 素材场景中光线烘焙后灯光失效
  • ¥15 请教一下各位,为什么我这个没有实现模拟点击
  • ¥15 执行 virtuoso 命令后,界面没有,cadence 启动不起来
  • ¥50 comfyui下连接animatediff节点生成视频质量非常差的原因
  • ¥20 有关区间dp的问题求解
  • ¥15 多电路系统共用电源的串扰问题
  • ¥15 slam rangenet++配置