woj部分题解：https://github.com/GonewithGt/woj

Description

平面上有n个点。给你一个半径为r的圆，问最多能覆盖多少个点（圆周上的点能够被覆盖）

Input

本题有多组测试数据，请处理到EOF
每组数据第一行有两个整数n，r，表示平面上点的个数和圆的半径。
0<=n<=200,1<=r<=1000
接下去n行每行有两个整数xi,yi，分别为n个点的坐标，-10000<=xi,yi<=10000

Output

对每组输入，输出这个圆最多能覆盖多少个点

Sample Input

Sample Output

Ans

C++

/*
    临界情况是两个点在圆上，任意变动一下圆心有一个点会在圆外。
    每次确定两个点，枚举所有的情况，确定圆心，取点在圆内最多
    的情况。注意两个点可以确定两个圆心的位置。
*/

#include<iostream>  
#include<cmath>  
using namespace std;  
#define eps 1e-8  
int r,N;  

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

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

 Point get_centerpoint(Point p1,Point p2)  
 {  
     Point mid = Point((p1.x+p2.x)/2,(p1.y+p2.y)/2); 
     double d = sqrt(r*r-pow(get_dist(p1,mid),2));  
     double angle = atan2(p1.x-p2.x,p2.y-p1.y);  
     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;  
 }  

void solve(int n,int r){
     int i,j;  

     int res = 0;  
     for(i=0;i<N;i++)  
     {  
         for(j=0;j<N;j++)  
         {  
             if(get_dist(points[i],points[j]) > 2.0*r) continue;  
             Point c = get_centerpoint(points[i],points[j]);  
             int count = 0;  
             for(int k=0;k<N;k++)  
                 if(get_dist(c,points[k]) < 1.0*r+eps) count++;  
             res = max(res,count);  
         }  
     }  
     cout<<res<<endl;  
 }

int main(){  

     while(cin>>N>>r){ 
       for(int i=0;i<N;i++)  
         cin>>points[i].x>>points[i].y;  

     solve(N,r);

     }
     return 0;  
 }