文章目录
  1. 1.
    1. 1.1. 读入坑
    2. 1.2. rand()坑
  2. 2. 附录
    1. 2.1. 四鸡落圆实验

引言:一些OJ中的坑。


读入坑

http://acm.hdu.edu.cn/showproblem.php?pid=1283

最简单的计算机

喵老板又指导了我一波。

这是一道最简单的签到题,但让我吃到了教训。

当scanf()和gets()混用,或cin()和getline()混用时候,一定要在scanf()和gets()之间加一个getchar()或cin.get()。

这个坑之前也踩过,现在又遇到了,做这道题不亏。

rand()坑

在四鸡落圆实验中遇到的。

rand()产生随机数的范围是0-32767,即一个short的非负数范围。

题目的答案在文末。

附录

四鸡落圆实验

计算机模拟:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include<bits/stdc++.h>
using namespace std;

struct coo{
double x,y;
coo operator - (const coo &b) const{
const coo &a=*this;
return coo{a.x-b.x,a.y-b.y};
}
};

const int n=4;
vector<coo> vec;

int z(double k){
if(fabs(k)<1e-8){
return 0;
}else if(k>0){
return 1;
}
return -1;
}

double xx(const coo &a,const coo &b){
return a.x*b.y-a.y*b.x;
}

pair<coo,coo> d(double k){
double x2=1.0/(k*k+1);
double y=sqrt(1.0-x2);
double x=sqrt(x2);
int sign=z(k);
return make_pair(coo{x,sign*y},coo{-x,-sign*y});
}

bool rectCross(const coo &a,coo &b,const coo &c,coo &d){//快速排斥实验
return min(a.x,b.x)<=max(c.x,d.x)&&
min(a.y,b.y)<=max(c.y,d.y)&&
min(c.x,d.x)<=max(a.x,b.x)&&
min(c.y,d.y)<=max(a.y,b.y);
}

bool segmentCross(const coo &a,coo &b,const coo &c,coo &d){//跨立实验
return (z(xx(c-a,d-a))^z(xx(c-b,d-b)))<0&&(z(xx(a-c,b-c))^z(xx(a-d,b-d)))<0;
}

bool cross(const coo &a,coo &b,const coo &c,coo &d){
return rectCross(a,b,c,d)&&segmentCross(a,b,c,d);
}

bool solve(){//返回true,则找到一个划分方法,使得n只鸭子落在同一个半圆内
for(int i=0;i<n;i++){
for(int j=i+1;j<n;j++){
double nume=vec[i].y-vec[j].y;
double denom=vec[i].x-vec[j].x;
double k=nume/denom;
if(((z(nume)^z(denom))<0 && k>0)||((z(nume)^z(denom))>0 && k<0)){//爆double了
printf("%f/%f=%f",nume,denom,k);
exit(1);
}
pair<coo,coo> res=d(k);//找到斜率为k的直径与圆的两个交点
bool ans=true;
for(int f=0;f<n;f++){
for(int g=f+1;g<n;g++){
if(cross(res.first,res.second,vec[f],vec[g])){
ans=false;
break;
}
}
}
if(ans){
return true;
}
}
}
return false;
}

const int precision=32767;//rand()产生0-32767的随机数
double RAND(){
return double(rand()%(precision+1))/precision;
}

int main(){
int N=100000;
srand(time(0));
int cnt=0;
for(int j=0;j<N;j++){
vec.clear();
for(int i=0;i<n;i++){//随机n只鸭子
coo tmp;
int sign=RAND()>=0.5?1:-1;
tmp.x=sign*RAND();
sign=RAND()>=0.5?1:-1;
tmp.y=sign*RAND();
if(tmp.x*tmp.x+tmp.y*tmp.y>=1){//不在圆内,重新随机
i--;
continue;
}
vec.push_back(tmp);
}
if(solve()){
++cnt;
}
}
printf("%d/%d=%f\n",cnt,N,double(cnt)/N);
}

运行结果0.5。

数学大佬推算:

ans=n2n1ans=\frac {n} {2^{n-1}}

注意,下面的推导过程需要区分“圆上”和“圆内”。

事件A:“将4只鸭随机投放到圆内,4只鸭恰好在同一个半圆”。

事件B:“在圆上任选4个点,4个点连线的长度最小值小于二分之一周长(假设连线总是逆时针方向,共有4种连线起点的选择方式)”。

显然,两个事件发生的概率相同。

假设给圆设定一维坐标系,坐标逆时针增大。

记连线为[a,b][a,b],其中aba\leqslant b,且baC2b-a\leqslant \frac C 2,其中C为周长。4个点中任意一个点的坐标值都有可能成为a的取值,因此选取方法有4种。此时重新以a为原点建立坐标系,即可满足对任意的坐标,都有aba\leqslant b,因为此时a=0 and b0a=0 ~\text{and}~b\geqslant0

剩余3个点能够落在我设定的半个周长长度的连线区间,从而使得该连线能够使事件成立的概率为123\frac 1 {2^3},计算有4×123=124\times \frac 1 {2^3}=\frac 1 2

推而广之,n只鸭子的情况下,可得到上式。

文章目录
  1. 1.
    1. 1.1. 读入坑
    2. 1.2. rand()坑
  2. 2. 附录
    1. 2.1. 四鸡落圆实验