Random Point in Triangle
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/contest/881/F
题意
有一个三角形,在其中任意选一点P,定义其v为P分割出的三个小三角形中面积最大值,问v期望。
思路
学会了个套路,不会算的话就模拟,答案一定是正比于总面积,计算系数就行了。
一个测试程序:
随机生成一个三角形内部的点。
可以用海伦公式计算出里面的点和三顶点围成的面积。
然后三者取最大。(计算期望
#include<bits/stdc++.h> using namespace std; typedef long long ll; #ifndef ONLINE_JUDGE #define dbg(x...) do{cout << "\033[33;1m" << #x << "->" ; err(x);} while (0) void err(){cout << "\033[39;0m" << endl;} template<template<typename...> class T, typename t, typename... A> void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);} template<typename T, typename... A> void err(T a, A... x){cout << a << ' '; err(x...);} #else #define dbg(...) #endif #define inf 1ll << 50 struct node { double x, y; node(double x = 0, double y = 0): x(x), y(y) {} }; double dis(node a, node b) { return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)); } double s(node a, node b, node c) { double ab = dis(a, b); double bc = dis(b, c); double ac = dis(a, c); double p = (ab + bc + ac) / 2; return sqrt(p * (p - ab) * (p - bc) * (p - ac)); } int main() { node p1 = node(0, 0); node p2 = node(1, 1); node p3 = node(2, 0); int t = 10000000; double cur = 0, ans = 0.0; srand((unsigned)time(NULL)); while (t--) { double x, y; double ss; while (1) { x = rand() % 1000000 * 2.0 / 1000000.0; y = rand() % 1000000 * 1.0 / 1000000.0; node nn = node(x, y); ss = max(s(p1, p2, nn), max(s(p1, p3, nn), s(p2, p3, nn))); if (isnan(ss)) continue; if (y >= 0 && x + y <= 2 && y - x <= 0) break; } cur += ss; if (cur >= 1000000.0) { ans += cur / 10000000.0; cur = 0.0; } } //printf("%.6f %.6f\n", ans, cur); ans += (double)cur / 10000000.0; printf("%.6f\n", ans * 36.0); return 0; }
#include <bits/stdc++.h> using namespace std; typedef long long ll; int main() { ll x1, x2, x3, y1, y2, y3; while (scanf("%lld%lld%lld%lld%lld%lld", &x1, &y1, &x2, &y2, &x3, &y3) != EOF) { double S = 0.0; ll ans = 0; ans = 11 * ((x1 * y2 + y1 * x3 + x2 * y3) - (x1 * y3 + y2 * x3 + y1 * x2)); ans = abs(ans); printf("%lld\n", ans); } return 0; }