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;
}

全部评论

相关推荐

比亚迪 求帮选offer 12k*1.36*12 双非硕
点赞 评论 收藏
转发
点赞 收藏 评论
分享
牛客网
牛客企业服务