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
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥100 有人会搭建GPT-J-6B框架吗?有偿
  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名