Nowcoder9983C.重力追击（暴力+少用sqrt）

链接：https://ac.nowcoder.com/acm/contest/9983/C
来源：牛客网

在一个二维平面上有 $ii个敌人可以描述为一个以(xi,yi)(x_{i},y_{i})(xi,yi)为圆心，rir_{i}ri为半径的圆。你每次可以对一个半径为Rmathit RR的圆范围内进行攻击（圆心自选，但圆心的横纵坐标必须为整数），对于与你攻击范围有交点的敌人都会被消灭。你总共可以发动kmathit kk次攻击，问最多能消灭多少敌人。$

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int n,k,x[maxn],y[maxn],r[maxn],R;
double getDis (int A,int B,int C,int D) {
    return ((A-C)*(A-C)+(B-D)*(B-D));
}
int main () {
    //对每一组敌人
    //如果它们距离一个整数点的距离都小于R 
    //说明可以消灭
    //14*14*1000*1000
    scanf("%d%d%d",&n,&k,&R);
    for (int i=1;i<=n;i++) scanf("%d%d%d",x+i,y+i,r+i); 
    if (k==3) {
        int ans=0;
        for (int ax=-7;ax<=7;ax++) {
            for (int ay=-7;ay<=7;ay++) {
                for (int bx=-7;bx<=7;bx++) {
                    for (int by=-7;by<=7;by++) {
                        for (int cx=-7;cx<=7;cx++) {
                            for (int cy=-7;cy<=7;cy++) {
                                int sum=0;
                                for (int i=1;i<=n;i++) {
                                    if (getDis(x[i],y[i],ax,ay)<=(R+r[i])*(R+r[i])) sum++;
                                    else if (getDis(x[i],y[i],bx,by)<=(R+r[i])*(R+r[i])) sum++;
                                    else if (getDis(x[i],y[i],bx,cy)<=(R+r[i])*(R+r[i])) sum++;
                                }
                                ans=max(ans,sum);
                            }
                        }
                    }
                }
            }
        }
        printf("%d
",ans);
        return 0;    
    }
    if (k==2) {
        int ans=0;
        for (int ax=-7;ax<=7;ax++) {
            for (int ay=-7;ay<=7;ay++) {
                for (int bx=-7;bx<=7;bx++) {
                    for (int by=-7;by<=7;by++) {
                        int sum=0;
                        for (int i=1;i<=n;i++) {
                            if (getDis(x[i],y[i],ax,ay)<=(R+r[i])*(R+r[i])) sum++;
                            else if (getDis(x[i],y[i],bx,by)<=(R+r[i])*(R+r[i])) sum++;
                        }
                        ans=max(ans,sum);
                    }
                }
            }
        }
        printf("%d
",ans);
        return 0;    
    }
    if (k==1) {
        int ans=0;
        for (int ax=-7;ax<=7;ax++) {
            for (int ay=-7;ay<=7;ay++) {
                int sum=0;
                for (int i=1;i<=n;i++) {
                    if (getDis(x[i],y[i],ax,ay)<=(R+r[i])*(R+r[i])) sum++;
                }
                ans=max(ans,sum);
            }
        }
        printf("%d
",ans);
        return 0;    
    }
}