2017CCPC秦皇岛 M题Safest Buildings&&ZOJ3993【复杂模拟】

题意：

给出两个半径R，r，R表示第一次的大圈半径，r表示第二次的小圈半径。第一次大圈的圆心位于（0，0），第二次小圈的圆心未知，但在大圈内，给你一个n,然后给出n个屋子的位置，问这些屋子中，第二次在小圈的概率最大的屋子有几个，都是哪些。

思路：

首先分析到如果小圈是一个很小很小的圈，那么靠近原点的区域的这些点的概率是一样的，因为都可以使小圈360度绕着这个点旋转。那么接着分析，如果小圈是个较大的圆，那么原点（0，0）可能是100%被包含的，那么就要找到这个临界情况，发现当R=2*r时，原点是恰好100%被包括的。那么这道题就可以解了。
注意输出，行末没空格。

代码：

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;
double eps=1e-8;

struct Point
{
    double x,y,dis;
}a[5050];
int ans[5050];

int main()
{
    int t,n;
    double R,r;
    cin>>t;
    while(t--)
    {
        scanf("%d%lf%lf",&n,&R,&r);
        double ansr;
        if(R>=2*r)
            ansr=R-2*r;
        else ansr=2*r-R;
        int j=0,flag=0;
        double maxn=9999999;
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&a[i].x,&a[i].y);
            a[i].dis=sqrt(a[i].x*a[i].x+a[i].y*a[i].y);
            if(a[i].dis<maxn)
                maxn=a[i].dis;
            if(a[i].dis<=ansr)
            {
                flag=1;ans[j++]=i+1;
            }
        }
        if(flag)
        {
            printf("%d
%d",j,ans[0]);
            for(int i=1;i<j;i++)
                printf(" %d",ans[i]);
                printf("
");
        }
        else
        {
            int j=0;
            for(int i=0;i<n;i++)
            {
                if(fabs(a[i].dis-maxn)<eps)
                    ans[j++]=i+1;
            }
            printf("%d
%d",j,ans[0]);
            for(int i=1;i<j;i++)
                printf(" %d",ans[i]);
                printf("
");
        }
    }
    return 0;
}

2017CCPC秦皇岛 M题Safest Buildings&&ZOJ3993【复杂模拟】

相关推荐