【题目描述】：
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
#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;
}
思路：对于输入的n个点，分别算出两坐标点之间的距离，若距离大于炸弹的半径则忽略，否则计算出以这两点为弦的圆的中心的坐标。然后以
圆中心为定点，分别计算出它与所有坐标点的距离并且与炸弹的半径比较。若不大于此半径则数量加一。
#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;
}