原文鏈接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-I.html

題目傳送門 - 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; }

　　

?

轉載于:https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-I.html

總結

以上是生活随笔為你收集整理的2018牛客网暑假ACM多校训练赛（第三场）I Expected Size of Random Convex Hull 计算几何,凸包,其他...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。