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

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条回答 默认 最新

相关推荐