2020ICPC·小米 网络选拔赛热身赛K-Random Point in Triangle

传送门:https://ac.nowcoder.com/acm/contest/8409/K

题意

给3个点$(x1,y1),(x2,y2),(x3,y3)$,在三角形内部中取一点p,设$E=max(S_{PAB},S_{PAC},S_{PBC})$,求E的概率期望。

思路

对于任何三角形,先看看特殊的等边三角形。然后在推广到任意三角形(ACM需要猜!)

O点为三角形ABC的内心。所以对于p的位置的选取,只需要在三角形的一半,然后一半即可。即在三角形OSB中选取。

$然后构造下图为:$

设该等边三角形的边长为2a,ON为y,NP为x,则根据相似可得:

$PH=\frac{2}{3}a+x+\frac{\sqrt 3}{3}y$ $PG=\frac{\sqrt 3}{2}PH=\frac{\sqrt3}{3}a+\frac{\sqrt 3}{2}x+\frac{1}{2}y$

$则E=S_{PAC}=\frac{1}{2}*AH*PG=\frac{\sqrt3}{3}a^2+\frac{\sqrt 3}{2}ax+\frac{1}{2}ay$

根据上图,P点的y可在$[0,\frac{\sqrt a}{3}a]$中选取,所以x可以在$[0,\sqrt 3y]$中选取。

对面积积分如下:

$$\int_{0}^{\frac{\sqrt a}{3}}dy\int_{0}^{\sqrt 3y}(\frac{\sqrt3}{3}a^2+\frac{\sqrt 3}{2}ax+\frac{1}{2}ay)dx=\frac{11}{36}a^4$$

而P点在该区域的选取面积为$\frac{\sqrt 3}{6}a^2$,期望为$\frac{11}{18}\sqrt 3 a^2$,而等边三角形的面积为$\sqrt 3a^2$ 即期望为$\frac{11}{18}S_{ABC}$,在乘以36得$22S_{ABC}$。

把等边三角形推广到任意三角形,虽然我不会证明,大胆猜测总没错!

Code

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
##include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pdd;

##define INF 0x3f3f3f3f
##define lowbit(x) x & (-x)
##define mem(a, b) memset(a , b , sizeof(a))
##define FOR(i, x, n) for(int i = x;i <= n; i++)

// const ll mod = 998244353;
const ll mod = 1e9 + 7;
// const double eps = 1e-6;
// const double PI = acos(-1);
// const double R = 0.57721566490153286060651209;

void solve() {
ll x1, x2, x3, y1, y2, y3;
while(cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3) {
cout << abs(x1 * y2 - x2 * y1 + x3 * y1 - x1 * y3 + x2 * y3 - x3 * y2) * 11 << endl;
}
}

signed main() {
ios_base::sync_with_stdio(false);
//cin.tie(nullptr);
//cout.tie(nullptr);
##ifdef FZT_ACM_LOCAL
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
signed test_index_for_debug = 1;
char acm_local_for_debug = 0;
do {
if (acm_local_for_debug == '$') exit(0);
if (test_index_for_debug > 20)
throw runtime_error("Check the stdin!!!");
auto start_clock_for_debug = clock();
solve();
auto end_clock_for_debug = clock();
cout << "Test " << test_index_for_debug << " successful" << endl;
cerr << "Test " << test_index_for_debug++ << " Run Time: "
<< double(end_clock_for_debug - start_clock_for_debug) / CLOCKS_PER_SEC << "s" << endl;
cout << "--------------------------------------------------" << endl;
} while (cin >> acm_local_for_debug && cin.putback(acm_local_for_debug));
##else
solve();
##endif
return 0;
}

本文作者:jujimeizuo
本文地址https://blog.jujimeizuo.cn/2020/10/24/2020-icpc-xiaomi-k/
本博客所有文章除特别声明外,均采用 CC BY-SA 3.0 协议。转载请注明出处!