根据网上的思路写了下代码,测试了几个用例都没问题,哪个大神帮忙看下哪里有问题啊。。。
题意:假设海岸线是一条无限延伸的直线。陆地在海岸线的一侧,而海洋在另一侧。每一个小的岛屿是海洋上的一个点。雷达坐落于海岸线上,只能覆盖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;
}