Codeforces 559D Randomizer

一句话题面

给出一个个点凸多边形，由凸多边形顶点构成的所有多边形将会被等概率的选到，求期望选到的多边形内部的整点有多少个？(3 \le n \le  100000)$

题解

假设最终答案为 ，即所有多边形内部的点数除以所能选出的多边形的个数(记为)。我们可以将其转化为整个多边形内部的点数（记为）乘以能选出多边形的个数再减去每个多边形选不到的点数之和（记为），即 。

对于能选出多边形的个数 ，考虑 个点，对于产生的 种选法，减去不选点的 种，选一个点的 种，选两个点的 种。因此共有 种多边形。

再考虑 ，我们可以考虑多边形能选到的每一条线求构成的多边形个数，同时它一侧的整点（包括线上的）将不会被它构成的多边形选到。对于一条线 ，它能构成的多边形个数为该线另一侧由 个点，则有 种选法，其中要减去一个点都不选的情况。因此，我们可以枚举每两个点构成的线，再将算出的一侧的点数乘上概率 ，最后再用 去减即可。

最后，对于多边形内部的点数，可由皮克公式得出。此时复杂度为 ，但发现当 足够大时，选该条线的概率大小将会十分小， 不计算不会影响精度。因此，我们可以将 限制在某个常量以内，这样复杂度将会降到 。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int MAXN = 100000 + 10;
const int EPS = 100;

struct Point{ double x, y; } P[MAXN], L, R, T;
Point operator - (Point& A,Point& B) { return (Point){A.x - B.x, A.y - B.y}; }

LL Gcd(LL a,LL b) { return b == 0? a: Gcd(b, a % b); }
double Cross(Point A,Point B) { return A.x * B.y - A.y * B.x; }

double p2[MAXN], Ans, Base, Area, S;
int N;LL pcnt, cur, bdcnt;

#define Pick(S, b) (S + 1.0 - (b) * 0.5)
#define NXT(x)     ((x + 1) % N)
#define gcd(x, y)  Gcd(abs(x), abs(y))
#define prob(k)    (N > EPS ? 1.0 / p2[k+1] : ((p2[N - (k) - 1] - 1.0) / Base))

int main(){
  if(fopen("input.txt","r")){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
  }

  scanf("%d", &N); p2[0] = 1.0;
  for(int i = 0;i < N; ++i){
    scanf("%lf%lf", &P[i].x, &P[i].y);
    p2[i + 1] = p2[i] * 2.0;
  }

  Base = p2[N] - 1 - N - 0.5 * N * (N - 1);

  R = P[N - 1] - P[0];
  bdcnt += gcd(R.x, R.y);
  R = P[1] - P[0];
  bdcnt += gcd(R.x, R.y);

  for(int i = 2;i < N; ++i){
    L = P[i] - P[0]; T = P[i] - P[i - 1];
    Area += Cross(R, L) * 0.5;
    bdcnt += gcd(T.x, T.y);
    R = L;
  }

  for(int i = 0;i < N; ++i){
    R = P[NXT(i)] - P[i]; pcnt = gcd(R.x, R.y); S = 0;
    for(int j = NXT(NXT(i)), k = 2;k <= 35 && NXT(j) != i; ++k,j = NXT(j)){
      L = P[j] - P[i]; T = L - R; pcnt += (cur = gcd(L.x, L.y)) + gcd(T.x, T.y);
      S += Cross(R, L) * 0.5;
      Ans += (Pick(S, pcnt) + (NXT(j) == i ? 0 : cur - 1)) * prob(k);
      R = L; pcnt -= cur;
    }
  }

  printf("%.10lf", Pick(Area, bdcnt) - Ans);
  return 0;
}