2 chengxunyuanzaza chengxunyuanzaza 于 2014.10.07 22:00 提问

C++关于炸弹袭击问题,求解!完全没头绪啊,麻烦各位给下思路或者代码我研究。。

【题目描述】:
H族的领地是一片富饶之地,有丰富的资源,无数的黄金。尽管异族侵略者被压制几百多年,他们并没有放弃对这片土地的渴望。最近,他们研制了一枚重磅炸弹。试图用它摧毁H族的防御工事。H族的防御工事由多个基地构成,侵略者试图用炸弹摧毁尽量多的防御基地,现在,他们急需你的帮助。如果你能为他们解决难题,会有巨大的奖励。(该炸弹的攻击范围是一个半径为r单位的圆)

【输入】
第一行为样例的个数T。
每个样例中有若干行,第一行为炸弹的攻击半径r,r有可能不是整数(1<=r<=100)
第二行是一个整数n,表示H族防御基地的个数(1<=n<=100)
接下来n行,每行有两个数,代表H族某个防御基地的坐标

【输出】
只有一个数,代表炸弹能最多摧毁的H族防御基地数量。

【输入样例】
1
1
3
1 0
0 1
4 0

【输出样例】
2

4个回答

devmiao
devmiao   Ds   Rxr 2014.12.13 00:59

#include
#include
using namespace std;
#define eps 1e-8
int r,num;

struct Point
{
double x,y;
Point(){}
Point(double tx,double ty){x=tx;y=ty;}
}p[200];

double dist(Point p1,Point p2)
{
return sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2));
}

Point GetCircleCenter(Point p1,Point p2)
{
Point mid = Point((p1.x+p2.x)/2,(p1.y+p2.y)/2);
double angle = atan2(p1.x-p2.x,p2.y-p1.y);
double d = sqrt(r*r-pow(dist(p1,mid),2));
return Point(mid.x+d*cos(angle),mid.y+d*sin(angle));
}

int max(int a,int b)
{
if(a>b)
return a;
return b;
}

int main()
{
int n;
cin>>n;
while(n--)
{

cin>>r;
cin>>num;
int i,j;
for(i=0;i cin>>p[i].x>>p[i].y;
int ans = 1;
for(i=0;i {
for(j=i+1;j {
if(dist(p[i],p[j]) > 2.0*r) continue;
Point center = GetCircleCenter(p[i],p[j]);
int cnt = 0;
for(int k=0;k<num;k++)
if(dist(center,p[k]) < 1.0*r+eps) cnt++;
ans = max(ans,cnt);
}
}
cout<<ans<<endl;
}
return 0;
}

devmiao
devmiao   Ds   Rxr 2014.12.13 01:00
yysave
yysave   2014.10.18 22:34

#include
#include
using namespace std;
#define eps 1e-8
int r,num;

struct Point
{
double x,y;
Point(){}
Point(double tx,double ty){x=tx;y=ty;}
}p[200];

double dist(Point p1,Point p2)
{
return sqrt(pow(p1.x-p2.x,2)+pow(p1.y-p2.y,2));
}

Point GetCircleCenter(Point p1,Point p2)
{
Point mid = Point((p1.x+p2.x)/2,(p1.y+p2.y)/2);
double angle = atan2(p1.x-p2.x,p2.y-p1.y);
double d = sqrt(r*r-pow(dist(p1,mid),2));
return Point(mid.x+d*cos(angle),mid.y+d*sin(angle));
}

int max(int a,int b)
{
if(a>b)
return a;
return b;
}

int main()
{
int n;
cin>>n;
while(n--)
{

cin>>r;
cin>>num;
int i,j;
for(i=0;i cin>>p[i].x>>p[i].y;
int ans = 1;
for(i=0;i {
for(j=i+1;j {
if(dist(p[i],p[j]) > 2.0*r) continue;
Point center = GetCircleCenter(p[i],p[j]);
int cnt = 0;
for(int k=0;k<num;k++)
if(dist(center,p[k]) < 1.0*r+eps) cnt++;
ans = max(ans,cnt);
}
}
cout<<ans<<endl;
}
return 0;
}

zxt_1
zxt_1   2014.12.13 00:43

思路:对于输入的n个点,分别算出两坐标点之间的距离,若距离大于炸弹的半径则忽略,否则计算出以这两点为弦的圆的中心的坐标。然后以
圆中心为定点,分别计算出它与所有坐标点的距离并且与炸弹的半径比较。若不大于此半径则数量加一。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!