[HDU3356 Air Strike]枚举、面积分配

【题目大意】

给定两个圆心，两圆的面积和，以及N个点的坐标。给出最小有多少个点不能覆盖到。

【算法分析】

枚举“卡住”第一个圆的是哪个点，然后把剩下的面积分到另外一个圆去。

【其它】注意，第一个圆的半径可以为0….比赛的时候就因为这个没A

【CODE】

#include #include #include #include #include #define sqr(x) ((x)*(x))
using namespace std;
const double pi=3.141;
const double eps=1e-8;
const int N=1111;
int n;
double lx[N],ly[N],sum,s1,s2,r1,r2;

inline double dis(int i,int j){
    return sqr(lx[i]-lx[j])+sqr(ly[i]-ly[j]);
}   

int main(){
    int Tc=0,now,ans;
    for (;;){
        scanf("%d",&n);
        if (!n) break;
        Tc++; ans=0;
        scanf("%lf%lf%lf%lf%lf",&lx[n+1],&ly[n+1],&lx[n+2],&ly[n+2],&sum);
        for (int i=1;i<=n;i++) scanf("%lf%lf",&lx[i],&ly[i]);
        for (int i=1;i<=n+1;i++){
            r1=dis(i,n+1);
            s1=r1*pi;
            if (s1>sum+eps) continue;
            s2=sum-s1+eps;
            r2=s2/pi;
            now=0;
            for (int j=1;j<=n;j++)
              if (dis(j,n+1)<=r1+eps || dis(j,n+2)<=r2+eps) now++;
            ans=max(now,ans);
        }   
        cout << Tc << ". " << n-ans << endl;
    }   
}