zoj 3993 Safest Buildings（几何+思维）

链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5639

题意：吃鸡游戏： 现在有一个半径为R的圈，圆心在 0 0 ，现在随机缩圈 变成一个半径为r 的圈 （r<=R）,大圈里有n 个建筑物，如果缩圈后建筑物在小圈里才算是安全，问你哪个建筑物的安全的概率最高，当然可能不止一个。

思路： 第一 ： 如果该建筑物的半径为 r 的圆上的点作半径为r的圆并且都在大园内。那么肯定 概率最大，既 dis+ r*2 <=R dis 表示该点到0 0  的距离。

第二： 如果没有第一种的情况，那么肯定谁离圆心近，谁的概率大。

第三： 如果r==R 那么所有点的都安全。

并且  注意精度  所以不要开根号。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 105;
const double eps= 1e-3;

struct node
{
    double x,y;
    double dis;
    int flag;
}a[N];

double R,r;
int n;

double init(double x,double y)
{
    return x*x+y*y;
}

int jud(int i)
{
    double tmp=R*R-4*R*r+4*r*r;
    if(a[i].dis<=tmp) return 1;
    return 0;
}

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d %lf %lf",&n,&R,&r);
        for(int i=1;i<=n;i++)
        {
            scanf("%lf %lf",&a[i].x, &a[i].y);
            a[i].dis=init(a[i].x,a[i].y);
            a[i].flag=0;
        }

        if(r==R)
        {
            printf("%d\n",n);
            for(int i=1;i<=n;i++)
            {
                if(i==n) printf("%d\n",i);
                else printf("%d ",i);
            }
            continue;
        }

        /*
        for(int i=1;i<=n;i++)
        {
            printf("***** %lf %lf %lf\n",a[i].x,a[i].y,a[i].dis);
        }
        */

        int flag=0;
        for(int i=1;i<=n;i++)
        {
            if(jud(i))
            {
                a[i].flag=1;
                flag=1;
            }
        }

        if(flag)
        {
            vector< int >ans;
            for(int i=1;i<=n;i++)
            {
                if(a[i].flag)
                {
                    ans.push_back(i);
                }
            }
            printf("%d\n",ans.size());
            for(int i=0;i<ans.size();i++)
            {
                if(i==ans.size()-1) printf("%d\n",ans[i]);
                else printf("%d ",ans[i]);
            }
        }
        else
        {
            double mn=1000000000.0;
            vector< int >ans;
            for(int i=1;i<=n;i++)
            {
                if(a[i].dis<mn)
                {
                    mn=a[i].dis;
                }
            }

            for(int i=1;i<=n;i++)
            {
                if(a[i].dis==mn)
                {
                    ans.push_back(i);
                }
            }
            printf("%d\n",ans.size());
            for(int i=0;i<ans.size();i++)
            {
                if(i==ans.size()-1) printf("%d\n",ans[i]);
                else printf("%d ",ans[i]);
            }
        }

    }
    return 0;
}

/*

2
3 10 5
3 4
3 5
3 6
3 10 4
-7 -6
4 5
5 4

*/