bzoj1913 signaling 信号覆盖 [思路题]

in 题目 with 0 comment

Description

1913_1.jpg


Input

输入第一行包含一个正整数 n, 表示房子的总数。接下来有 n 行,分别表示 每一个房子的位置。对于 i = 1, 2, .., n, 第i 个房子的坐标用一对整数 xi和yi来表 示,中间用空格隔开。


Output

输出文件包含一个实数,表示平均有多少个房子被信号所覆盖,需保证输出 结果与精确值的绝对误差不超过0.01。


Sample Input

4
0 2
4 4
0 0
2 0


Sample Output

3.500


HINT

3.5, 3.50, 3.500, … 中的任何一个输出均为正确。此外,3.49, 3.51,
3.499999,…等也都是可被接受的输出。
100%的数据保证,对于 i = 1, 2, .., n, 第 i 个房子的坐标(xi, yi)为整数且
$–1,000,000 ≤ xi, yi ≤ 1,000,000$. 任何三个房子不在同一条直线上,任何四个房子不
在同一个圆上;
40%的数据,$n ≤ 100$;
70%的数据,$n ≤ 500$;
100%的数据,$3 ≤ n ≤ 1,500$。


Solution

这道题的思路不是十分好想,首先分析题目,题目中要求的其实是任取坐标系内三个点,这三个点组成的外接圆所包含点的个数的数学期望.对于任意三个点做外接圆,我们讨论另一个点的情况:

  1. 第四个点与圆上三点组成凸多边形,如图,由于题目中限制没有任意四点共圆,所以这四个点会组成四个圆,而这四个圆中会额外包含一个点的有如图所示的两种情况,所以一个凸四边形对答案的贡献为2

  2. 同理,我们分析凹四边形,不难发现能组成的四个圆中额外包含一个点的只有1种情况,所以凹四边形对答案的贡献为1

  3. 知道这些之后,我们设凹多边形的个数为A,凸多边形的个数为B,易得$A+B=C_n^4$,并且所求期望$q=(A+2*B)/C_n^3+3$(切记要加三,因为无论怎么圈,都至少有三个点在园内,而我们在计算贡献时并没有加进去)

  4. 经过3的分析,我们只要求出凹多边形的个数就可以推出凸多边形的个数,进而得到原题的解,如何求凹多边形的个数呢?我们可以枚举每一个点为中心点,将剩余的点按照极角大小排序,找出与所选为中心点的极角相差超过pi的点的对数即可,设p为不包含中心点的三角形个数,则$B=C_{n-1}^3-p$

IMG_0303@0,5x.jpg


Code

#include<bits/stdc++.h>
#define maxn 1505
//#define DEBUG
using namespace std;
long long n,A=0,B;

struct Point
{
    long long x,y;
    double angel;
    Point(long long x=0,long long y=0):x(x),y(y) { } 
}p[maxn],a[maxn];

Point operator - (Point a,Point b) { return Point(a.x-b.x,a.y-b.y); }
bool operator < (Point a,Point b) { return a.angel<b.angel; }
long long Cross(Point a,Point b) { return a.x*b.y-a.y*b.x; }
double atan2(Point a) { return atan2(a.y,a.x); }

inline long long read()
{
    char ch;
    long long read=0,sign=1;
    do
        ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-');
    if(ch=='-') sign=-1,ch=getchar();
    while(ch>='0'&&ch<='9')
    {
        read=read*10+ch-'0';
        ch=getchar();
    }
    return sign*read;
}

long long solve(int x)
{
    long long tot=(n-1)*(n-2)*(n-3)/6;
    int cnt=0;
    for(int i=1;i<=n;++i)
    {
        if(i!=x) p[++cnt]=a[i];
        else p[0]=a[i];
    }
    for(int i=1;i<=cnt;++i) p[i].angel=atan2(p[i]-p[0]);
    sort(p+1,p+cnt+1);
#ifdef DEBUG
    cout<<"x="<<x<<endl;
    for(int i=1;i<=cnt;++i)
        cout<<"("<<p[i].x<<","<<p[i].y<<")"<<endl;
#endif 
    int t=0,R=2;
    for(int i=1;i<=cnt;++i)
    {
        while(Cross(p[i]-p[0],p[R]-p[0])>=0)
        {
            t++;
            R=R%cnt+1;
            if(R==i) break;
        }
        tot-=t*(t-1)/2;
        t--;
    }
    return tot;
}

int main()
{
    n=read();
    //if(n==3){printf("3.00\n");return 0;}
    for(int i=1;i<=n;++i) a[i].x=read(),a[i].y=read();
    for(int i=1;i<=n;++i) A+=solve(i);
    B=n*(n-1)*(n-2)*(n-3)/24-A;
    double ans=double(2*B+A)/double(n*(n-1)*(n-2)/6)+3.0;
    printf("%.3lf\n",ans);
    return 0;   
}

扫描二维码,在手机上阅读!
Responses