链接：https://ac.nowcoder.com/acm/contest/881/F
来源：牛客网
题目描述
Bobo has a triangle ABC with A(x1,y1),B(x2,y2)and C(x3,y3). Picking a point P uniformly in triangle ABC, he wants to know the expectation value E=max{SPAB,SPBC,SPCA} where SXYZ denotes the area of triangle XYZ.
Print the value of 36×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|≤10^8 * 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
结论就是三角形面积的22倍，下面是ac代码（写的一点都不好看）
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
ll x1,y11,x2,y2,x3,y3;
struct Point{
ll x;
ll y;
Point(){}
Point(ll a, ll b):x(a), y(b){}
}a,b,c;
ll s(Point &a,Point &b, Point &c){
ll ans=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)*11;//三角形面积的22倍
return ans;
}
ll S;
void init(){
a=Point(x1,y11);
b=Point(x2,y2);
c=Point(x3,y3);
S=s(a,b,c);
cout<<S<<endl;
}
int main(){
while(cin>>x1>>y11>>x2>>y2>>x3>>y3){
init();
}
return 0;
}
随机数猜结论（比ac代码重要多了）
c++随机数https://www.cnblogs.com/xiaokang01/p/9786751.html
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef long long ll;
double x1,y11,x2,y2,x3,y3;
struct Point{
double x;
double y;
Point(){}
Point(double a, double b):x(a), y(b){}
}a,b,c;
double cross(const Point &a, const Point &b, const Point &p) //叉乘
{
return (b.x - a.x)*(p.y - a.y) - (b.y - a.y)*(p.x - a.x);
}
bool toLeft(const Point &a, const Point &b, const Point &p) //判断p是否是在ab的左边
{
return cross(a, b, p) > 0;
}
bool inTriangle(const Point &p, const Point &a, const Point &b, const Point &c)
{
bool res = toLeft(a, b, p);
if (res != toLeft(b, c, p))
return false;
if (res != toLeft(c, a, p))
return false;
if (cross(a, b, c) == 0) //ABC is in one line
return false;
return true;
}
double s(Point &a,Point &b, Point &c){
double ans=fabs(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;
return ans;
}
double S;
void init(){ //建点和求三角形面积
a=Point(x1,y11);
b=Point(x2,y2);
c=Point(x3,y3);
S=s(a,b,c);
cout<<S<<endl;
}
int main(){
srand((unsigned)time(NULL));
while(cin>>x1>>y11>>x2>>y2>>x3>>y3){
init();
int cnt=0;
double ans=0;
for(int i=1;i<=10000000;i++){
double x=rand()/double(RAND_MAX)*10;
double y=rand()/double(RAND_MAX)*10;
Point p=Point(x,y);
if(inTriangle(p,a,b,c)){
cnt++;
ans+=max(s(p,a,b),max(s(p,a,c),s(p,b,c)));
}
}
double e=ans/cnt*36;
cout<<e<<" "<<e/S<<endl;
}
return 0;
}
/*
0 0 8 0 7 5
0 0 8 0 5 7
0 0 9 0 3 4
0 0 6 0 2 1
*/
京公网安备 11010502036488号