bzoj1913: [Apio2010]signaling 信号覆盖

传送门

题解传送门

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

#define pi acos(-1)

#define eps 1e-15

const int N=1e5+;

#define For(i,a,b) for(int i=(a);i<=(b);i++)

#define Rep(i,a,b) for(int i=(a);i>=(b);i--)

typedef long long LL;

typedef double db;

using namespace std;

int n,cnt;

LL c1,c2,tp;

db a[N],ans;

template<typename T>void read(T &x)  {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

struct pt {

    db x,y;

}p[N];

LL C(int n,int m) {

    LL rs=;

    Rep(i,n,n-m+) rs*=i;

    For(i,,m) rs/=i;

    return rs;

}

int main() {

    read(n); tp=C(n-,);

    For(i,,n) scanf("%lf%lf",&p[i].x,&p[i].y);

    For(i,,n) {

        cnt=;

        For(j,,n) if(j!=i)

            a[++cnt]=atan2(p[j].y-p[i].y,p[j].x-p[i].x);

        For(i,,cnt) {

            if(a[i]<) a[i]+=pi*;

            a[cnt+i]=a[i]+pi*;

        }

        sort(a+,a+*cnt+);

        int r=; c1=;

        For(l,,cnt) {

            while(r<*cnt&&a[r+]-a[l]<pi)

                r++;

            if(r-l) c1+=C(r-l,);

        }

        c2+=tp-c1;

    }

    ans=(db)(c2+(C(n,)-c2)*)/(db)C(n,)+;

    printf("%.6lf\n",ans);

    return ;

}