题意
给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 = 1e9 + 7;
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);
##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 协议。转载请注明出处！