2017-05-24 17:02

# poj 1328贪心算法，一直WA

#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
最佳回答
评论
解决 无用
打赏 举报