［BZOJ 1913］［Appio 2010］signaling信号カバー（幾何学＋合成数学の計算）

テーマの説明
コンベヤー？ドア
問題を解く
非常に不思議な問題です。最初はsb暴力という題名だけでよく説明できましたorz：http://blog.csdn.net/qpswwww/article/details/45334033
コード

#include
#include
#include
#include
#include
using namespace std;
#define N 1505

const double pi=acos(-1.0);
const double eps=1e-9;
int dcmp(double x)
{
    if (x<=eps&&x>=-eps) return 0;
    return (x>0)?1:-1;
}
struct Point{double x,y;};
int n;
double ang[N+N],ao,tu,ans;
Point p[N];

double C(int n,int m)
{
    if (m>n) return 0.0;
    double ans=1.0;
    for (int i=n-m+1;i<=n;++i)
        ans*=(double)i;
    for (int i=1;i<=m;++i)
        ans/=(double)i;
    return ans;
}
double calc(int id)
{
    int cnt=0;
    for (int i=1;i<=n;++i)
        if (id!=i)
            ang[++cnt]=atan2(p[i].y-p[id].y,p[i].x-p[id].x);
    sort(ang+1,ang+cnt+1);
    for (int i=1;i<=cnt;++i) ang[cnt+i]=ang[i]+2*pi;
    double ans=0;
    int l=1,r=1;
    while (l<=cnt)
    {
        r=max(r,l+1);
        while (r<=cnt*2&&ang[r]1,2);
        ++l;
    }
    return C(n-1,3)-ans;
}
int main()
{
    scanf("%d",&n);
    if (n==3) {puts("3.000000");return 0;}
    for (int i=1;i<=n;++i) scanf("%lf%lf",&p[i].x,&p[i].y);
    for (int i=1;i<=n;++i)
        ao+=calc(i);
    tu=C(n,4)-ao;
    ans=(ao+2*tu)/C(n,3)+3.0;
    printf("%.6lf
",ans);
}