2019牛客多校第一场 F Random Point in Triangle 随机数出结论

链接：https://ac.nowcoder.com/acm/contest/881/F
来源：牛客网

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 524288K，其他语言1048576K
64bit IO Format: %lld

题目描述

Bobo has a triangle ABC with A(x1,y1),B(x2,y2)A(x1,y1),B(x2,y2) and C(x3,y3)C(x3,y3). Picking a point P uniformly in triangle ABC, he wants to know the expectation value E=max{SPAB,SPBC,SPCA}E=max{SPAB,SPBC,SPCA} where SXYZSXYZ denotes the area of triangle XYZ.

Print the value of 36×E36×E. It can be proved that it is always an integer.

输入描述:

The input consists of several test cases and is terminated by end-of-file.

Each test case contains six integers x1,y1,x2,y2,x3,y3x1,y1,x2,y2,x3,y3.

* |x1|,|y1|,|x2|,|y2|,|x3|,|y3|≤108|x1|,|y1|,|x2|,|y2|,|x3|,|y3|≤108
* There are at most 105105 test cases.

输出描述:

For each test case, print an integer which denotes the result.

示例1

输入

复制

0 0 1 1 2 2
0 0 0 0 1 1
0 0 0 0 0 0

输出

复制

0
0
0

题目大意: 给你三角形三个顶点的坐标,问如果在三角形内部选取一点,使得max{sPAB,sPBC,sPAC}最大.

题目思路:很多大佬这个题已经用数学方法推出来了,但这个题可以用随机数把答案跑出来,所以借此题了解一下随机数出结论的方法:

产生两个double 类型随机数,当做P点的横纵坐标,然后判断是否在三角形内,如果在三角形内就求一遍面积取最大,最后取平均值就是数学期望,这个期望在n越大的情况下越准确,所以就可以得出答案了.具体细节和注释看代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e9+5;
const int maxn=1e6+8;
const double PI=acos(-1);
const ll mod=1000000007;
ll n,m;
ll x1,yy,x2,y2,x3,y3;
struct node{
    double x;
    double y;
}p1,p2,p3;
double cal(node a,node b,node p)//向量叉乘
{
    double x1=p.x-a.x,y1=p.y-a.y;
    double x2=b.x-p.x,y2=b.y-p.y;
    return x1*y2-x2*y1;
}
bool cross(node a,node b,node c)//判断是否在一条线的右边
{
    return cal(a,b,c)>0;
}
bool judge(node p,node a,node b,node c)
{
    bool res=cross(a,b,p);
    if(cross(b,c,p)!=res)
        return false;
    if(cross(c,a,p)!=res)
        return false;
    if(cal(a,b,c)==0)
        return false;
    return true;
}
double s(node a,node b,node c)
{
    return abs(a.x*b.y+b.x*c.y+c.x*a.y-a.x*c.y-b.x*a.y-c.x*b.y)/2;
}
void product()
{
    srand(time(0));
    double cnt=0,sum=0;
    for(int i=1;i<=10000000;i++)
    {
        node p;
        p.x=rand()/double((RAND_MAX))*10;//看你三角形横纵坐标的范围确定 *多少.
        p.y=rand()/double((RAND_MAX))*10;
       // printf("%lf %lf\n",p.x,p.y);
        if(judge(p,p1,p2,p3))
        {
            cnt++;
            sum+=max(s(p1,p,p3),max(s(p1,p,p2),s(p2,p,p3)));
            //printf("%lf",sum);
        }
    }
    printf("\n");
    printf("数学期望 %lf\n",sum/cnt*36);
    printf("\n该面积为三角形面积的 %.2lf倍.",sum/cnt/s(p1,p2,p3)*36);
}
int main()
{
    while(~scanf("%lf%lf%lf%lf%lf%lf",&p1.x,&p1.y,&p2.x,&p2.y,&p3.x,&p3.y))
    {
        product();
    }
}

总结:暑假训练有点nice,又get一个新知识点,继续加油!