【bzoj1913】 Apio2010—signaling 信号覆盖-白红宇

【bzoj1913】 Apio2010—signaling 信号覆盖

阅读量：5059 次

发布时间：2019-06-12

本文共 1093 字，大约阅读时间需要 3 分钟。

(题目链接)

题意

　　给出一个平面上n个点，求任选3个点画一个圆所包含的点的期望值。

Solution

　　这个问题可以转化为凹凸多边形的问题求解（当然我是没想到的）。。左转题解：

细节

　　注意存放极角的数组要开成2倍。

代码

// bzoj1913#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define LL long long#define inf 2147483640#define eps 1e-6#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;const int maxn=2000;struct point {int x,y;}p[maxn];LL C[maxn][maxn];double a[maxn<<1];int n;int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y); for (int i=0;i<=n;i++) C[i][0]=1; for (int i=1;i<=n;i++) for (int j=1;j<=i;j++) C[i][j]=C[i-1][j]+C[i-1][j-1]; LL t2,t1=0; for (int i=1;i<=n;i++) { int cnt=0; for (int j=1;j<=n;j++) if (i!=j) { a[++cnt]=atan2(p[j].y-p[i].y,p[j].x-p[i].x); if (a[cnt]<0) a[cnt]+=2*Pi; } sort(a+1,a+cnt+1); for (int j=1;j<=cnt;j++) a[j+cnt]=a[j]+2*Pi; for (int j=1,k=1;j<=cnt;j++) { while (a[k+1]-a[j]