题意
给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 协议。转载请注明出处!