2018牛客網暑假ACM多校訓練賽（第三場）I Expected Size of Random Convex Hull 計算幾何,凸包,其他

​題目傳送門 - 2018牛客多校賽第三場 I​​

題意

　　在一個給定的三角形内部随機選擇 $n$ 個點，問這些點構成的凸包的期望頂點數。

　　$3\leq n\leq 10$

題解

　　首先證明一個結論，對于任意三角形，随機撒 $n$ 個點的期望點數相同。

　　簡單口胡：考慮任意拉扯三角形，三角形内部多邊形的凸性都不會改變。

　　是以，我們隻需要随便選擇一個三角形，然後随機選點很多次，建出凸包，得到頂點數，然後算一算平均值，就可以得到答案了。

　　注意随機選點次數至少好幾億吧。

　　我賽後代碼跑了大約 25 分鐘才跑出來。

代碼1 - 打表

%:pragma GCC optimize("Ofast")
%:pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=20;
int n;
struct Point{
  int x,y;
  Point(){}
  Point(int _x,int _y){
    x=_x,y=_y;
  }
}P[N],O;
LL cross(Point a,Point b,Point c){
  return 1LL*(b.x-a.x)*(c.y-a.y)-1LL*(c.x-a.x)*(b.y-a.y);
}
int Drand(){
  return (int)((((rand()&32767)<<10)+(rand()&1024))&33554431);
}
LL sqr(int x){
  return 1LL*x*x;
}
LL dis(Point a,Point b){
  return sqr(a.x-b.x)+sqr(a.y-b.y);
}
bool cmp_O(Point a,Point b){
  if (a.y==b.y)
    return a.x<b.x;
  return a.y<b.y;
}
bool cmp_Angle(Point a,Point b){
  LL c=cross(O,a,b);
  if (c==0)
    return dis(O,a)<dis(O,b);
  return c>0;
}
int st[N],top;
int Convex(){
  for (int i=2;i<=n;i++)
    if (!cmp_O(P[1],P[i]))
      swap(P[1],P[i]);
  O=P[1];
  sort(P+2,P+n+1,cmp_Angle);
  top=0;
  st[++top]=1,st[++top]=2;
  for (int i=3;i<=n;i++){
    while (top>=2&&cross(P[st[top-1]],P[st[top]],P[i])<=0)
      top--;
    st[++top]=i;
  }
  return top;
}
int main(){
freopen("list.txt","w",stdout);
  srand(time(NULL));
for (int i=3;i<=10;i++){
  n=i;
  int tot=200000000,ttt=tot;
  int ans=0;
  while (tot--){
    for (int i=1;i<=n;i++)
      while (1){
        P[i]=Point(Drand(),Drand());
        if (P[i].y<=P[i].x)
          break;
      }
    ans+=Convex();
  }
  printf("%.6lf\n",((double)ans)/ttt);
}
  return 0;
}
      

　　

代碼2 - AC 代碼

#include <bits/stdc++.h>
using namespace std;
double ans[11]={
0,0,0,
3.000000,
3.666719,
4.166715,
4.566691,
4.899998,
5.185735,
5.435731,
5.657986
};
int main(){
  int n;
  for (int i=1;i<=7;i++)
    scanf("%d",&n);
  printf("%.6lf",ans[n]);
  return 0;
}