Random Point in Triangle【随机数解决期望值问题】

Random Point in Triangle

题目描述

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.

输入

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

输出

0
0
0

题目描述：

多组输入三角形各个顶点坐标p1,p2,p3，在三角形中任取一点p，计算期望E=max(S(p,p1,p2),max(S(p,p1,p3),S(p,p2,p3)));

思路：

1、产生随机点，选出在三角形内部的点，对每个符合条件的点分别求出最大面积并求和，最后取面积和的平均值即为期望E。（当随机数足够多时，所有最大面积和的平均值即为期望）

2、根据下面找规律代码可以求出：(由于是跑的随机数，结果定不完全等于22)

3、求出E后可以看出规律，即 36*E=22*S(p1,p2,p3)

补充：

1、根据三角形坐标求三角形面积：向量差乘求三角形面积

2、坐标点结构体：

struct poLL{
    LL x;
    LL y;
};
struct poLL p1,p2,p3,p;
p1.x=x1,p1.y=y1;
p2.x=x2,p2.y=y2;
p3.x=x3,p3.y=y3;

一看就能看懂，挺好用的，在传点坐标时不用分别传x、y了

找规律代码：

#include<bits/stdc++.h>
using namespace std;
struct point{
    double x;
    double y;
};
double S(point p1,point p2,point p3) ///向量叉乘求三角形面积可以看上面链接
{
    return fabs((p1.x-p3.x)*(p1.y-p2.y)-(p1.x-p2.x)*(p1.y-p3.y));
}

bool judge(point p,point p1,point p2,point p3) ///判断生成的随机点是不是在三角中 原理是：三个 
                                         ///小三角形面积之和是不是等于原来大的三角形面积
{
    if(S(p1,p2,p3)==(S(p1,p2,p)+S(p,p1,p3)+S(p2,p3,p))){
        //printf("*%lf %lf %lf %lf
",S(p1,p2,p3),S(p1,p2,p),S(p,p1,p3),S(p2,p3,p));
        return true;
    }
    return false;
}
int main()
{
    double x1,x2,x3,y1,y2,y3;
    while(scanf("%lf%lf%lf%lf%lf%lf",&x1,&y1,&x2,&y2,&x3,&y3)!=EOF){
        double cnt=0;
        struct point p1,p2,p3,p;
        p1.x=x1,p1.y=y1;
        p2.x=x2,p2.y=y2;
        p3.x=x3,p3.y=y3;
        srand(time(0));
        double sum=0;
        for(int i=0;i<100000000;i++){
            int x=rand();
            int y=rand();
            p.x=x*1.0,p.y=y*1.0;
            if(judge(p,p1,p2,p3)){
                cnt++;
                sum+=(max(S(p1,p2,p),max(S(p,p1,p3),S(p2,p3,p))));
            }
            //printf("%.3lf
",sum);
        }
        double S1=S(p1,p2,p3);
        double q=((sum/cnt)*36.0)/S1;
        printf("%.3lf
",q);
    }
    return 0;
}

AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct poLL{
    LL x;
    LL y;
};
LL S(poLL p1,poLL p2,poLL p3)
{
    return abs((p1.x-p3.x)*(p1.y-p2.y)-(p1.x-p2.x)*(p1.y-p3.y));
}
int main()
{
    LL x1,x2,x3,y1,y2,y3;
    while(scanf("%lld%lld%lld%lld%lld%lld",&x1,&y1,&x2,&y2,&x3,&y3)!=EOF){
        struct poLL p1,p2,p3,p;
        p1.x=x1,p1.y=y1;
        p2.x=x2,p2.y=y2;
        p3.x=x3,p3.y=y3;
        printf("%lld
",11*S(p1,p2,p3));
    }
    return 0;
}