2018牛客网暑假ACM多校训练赛(第三场)I Expected Size of Random Convex Hull 计算几何,凸包,其他

时间:2022-09-21 08:47:55

原文链接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;
}

  

2018牛客网暑假ACM多校训练赛(第三场)I Expected Size of Random Convex Hull 计算几何,凸包,其他的更多相关文章

  1. 2018牛客网暑假ACM多校训练赛(第二场)E tree 动态规划

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round2-E.html 题目传送门 - 2018牛客多校赛第二场 E ...

  2. 2018牛客网暑假ACM多校训练赛(第三场)G Coloring Tree 计数&comma;bfs

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-G.html 题目传送门 - 2018牛客多校赛第三场 G ...

  3. 2018牛客网暑假ACM多校训练赛(第三场)D Encrypted String Matching 多项式 FFT

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round3-D.html 题目传送门 - 2018牛客多校赛第三场 D ...

  4. 2018牛客网暑假ACM多校训练赛(第十场)H Rikka with Ants 类欧几里德算法

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round10-H.html 题目传送门 - https://www.n ...

  5. 2018牛客网暑假ACM多校训练赛(第十场)F Rikka with Line Graph 最短路 Floyd

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round10-F.html 题目传送门 - https://www.n ...

  6. 2018牛客网暑假ACM多校训练赛(第十场)D &Tab;Rikka with Prefix Sum 组合数学

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round10-D.html 题目传送门 - https://www.n ...

  7. 2018牛客网暑假ACM多校训练赛(第八场)H Playing games 博弈 FWT

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round8-H.html 题目传送门 - https://www.no ...

  8. 2018牛客网暑假ACM多校训练赛(第七场)I Tree Subset Diameter 动态规划 长链剖分 线段树

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round7-I.html 题目传送门 -  https://www.n ...

  9. 2018牛客网暑假ACM多校训练赛(第六场)I Team Rocket 线段树

    原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round6-I.html 题目传送门 - https://www.no ...

随机推荐

  1. 在 Java 代码中对 Kerberos 主体进行身份验证

    转载请注明出处:http://www.cnblogs.com/xiaodf/ 本文举例说明如何使用 org.apache.hadoop.security.UserGroupInformation 类在 ...

  2. Octopus系列之各个页面调用示例

    调用首页产品 可选参数如下 New = 1, Hot = 2, Best = 3, Special = 4, Featured = 5, Other = 6 #foreach($item in $oc ...

  3. iOS - Swift NSLocale&Tab;&Tab;本地化信息

    前言 public class NSLocale : NSObject, NSCopying, NSSecureCoding NSLocale 类返回本地化信息,主要体现在"语言" ...

  4. android上下文

    在android中常常会遇到与context有关的内容 浅论一下context : 在语句 AlertDialog.Builder builder = new AlertDialog.Builder( ...

  5. cx&lowbar;Oracle模块学习之绑定变量

    有些时候我们需要和程序交互,此时需要绑定量下面两个例子简介在SELECT 和 DML 里面绑定变量的用法 SELECT 里面的绑定变量 [root@Ora10G py]# cat SelectBind ...

  6. 光环国际的PRINCE2培训时间

    一.光环国际的PRINCE2课程安排培训方式:    小班授课,50人为限;   全国网址直播课程,覆盖各个地区学员    精读原理配合独家开发大量实际案例研讨;    从商业战略角度解析PRINCE ...

  7. Delphi窗体显示Echarts图表

    笨办法,先保存用着 unit Unit1; interface uses Winapi.Windows, Winapi.Messages, System.SysUtils, System.Varian ...

  8. 【Vagrant】-NO&period;130&period;Vagrant&period;2 -【Error&colon;the filesystem &quot&semi;vboxsf&quot&semi; is not available】

    Style:Mac Series:Java Since:2018-09-10 End:2018-09-10 Total Hours:1 Degree Of Diffculty:5 Degree Of ...

  9. Study 3 —— Python运算符

    参考资料:http://www.runoob.com/python/python-operators.html#ysf2 定义变量: a = 10, b = 20 算术运算符: 运算符   描述 实例 ...

  10. openjudge noi 鸡尾酒疗法

    题目链接:http://noi.openjudge.cn/ch0105/18/ 总时间限制: 1000ms 内存限制: 65536kB 描述 鸡尾酒疗法,原指“高效抗逆转录病毒治疗”(HAART),由 ...