题意：一个骰子在一个人正方形内，蜜蜂在任意一个位置可以出现，问看到点数的期望。
思路：半平面交+概率期望
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<string>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=1e5+;
const double eps=1e-;
const double pi=acos(-); double dcmp(double x)
{
if(fabs(x) < eps) return ;
else return x < ? - : ;
} struct Point
{
double x, y;
Point(double x=, double y=):x(x),y(y) { }
}; typedef Point Vector; Vector operator + (const Point& A, const Point& B)
{
return Vector(A.x+B.x, A.y+B.y);
} Vector operator - (const Point& A, const Point& B)
{
return Vector(A.x-B.x, A.y-B.y);
} Vector operator * (const Point& A, double v)
{
return Vector(A.x*v, A.y*v);
} Vector operator / (const Point& A, double v)
{
return Vector(A.x/v, A.y/v);
} double Cross(const Vector& A, const Vector& B)
{
return A.x*B.y - A.y*B.x;
} double Dot(const Vector& A, const Vector& B)
{
return A.x*B.x + A.y*B.y;
} double Length(const Vector& A)
{
return sqrt(Dot(A,A));
} Vector Rotate(Vector A,double rad)
{
return Vector(A.x*cos(rad)-A.y*sin(rad),A.x*sin(rad)+A.y*cos(rad));
} bool operator < (const Point& p1, const Point& p2)
{
return p1.x < p2.x || (p1.x == p2.x && p1.y < p2.y);
} bool operator == (const Point& p1, const Point& p2)
{
return p1.x == p2.x && p1.y == p2.y;
} Vector Normal(Vector A)
{
double L=Length(A);
return Vector(-A.y/L,A.x/L);
}
struct Line
{
Point P;
Vector v;
double ang;
Line() {}
Line(Point P, Vector v):P(P),v(v)
{
ang = atan2(v.y, v.x);
}
bool operator < (const Line& L) const
{
return ang < L.ang;
}
}; bool OnLeft(const Line& L, const Point& p)
{
return Cross(L.v, p-L.P) > ;
} Point GetLineIntersection(const Line& a, const Line& b)
{
Vector u = a.P-b.P;
double t = Cross(b.v, u) / Cross(a.v, b.v);
return a.P+a.v*t;
} const double INF = 1e8; Point ansPoly[maxn];
int HalfplaneIntersection(vector<Line> L) //L为切割平面的直线集合，求半平面交，返回点的个数，点存在anspoly数组中
{
int n = L.size();
sort(L.begin(), L.end()); // 按极角排序
int first, last; // 双端队列的第一个元素和最后一个元素的下标
vector<Point> p(n); // p[i]为q[i]和q[i+1]的交点
vector<Line> q(n); //
q[first=last=] = L[]; //
for(int i = ; i < n; i++)
{
while(first < last && !OnLeft(L[i], p[last-])) last--;
while(first < last && !OnLeft(L[i], p[first])) first++;
q[++last] = L[i];
if(fabs(Cross(q[last].v, q[last-].v)) < eps) //
{
last--;
if(OnLeft(q[last], L[i].P)) q[last] = L[i];
}
if(first < last) p[last-] = GetLineIntersection(q[last-], q[last]);
}
while(first < last && !OnLeft(q[first], p[last-])) last--; //
if(last - first <= ) return ; //
p[last] = GetLineIntersection(q[last], q[first]); //
// 从deque复制到输出中
int index=;
for(int i = first; i <= last; i++) ansPoly[index++]=p[i];
return index;
} double PolygonArea(int n,Point *p)
{
double area=;
for(int i=; i<n-; i++)
area+=Cross(p[i]-p[],p[i+]-p[]);
return area/;
}
// vector<Line> vec;
// vec.push_back(Line(Point(0,0),Point(1,0)));
// vec.push_back(Line(Point(10000,0),Point(0,1)));
// vec.push_back(Line(Point(10000,10000),Point(-1,0)));
// vec.push_back(Line(Point(0,10000),Point(0,-1)));
// Vector v=(p[1]-p[0]);
// vec.push_back(Line((p[1]+p[0])*0.5,Normal(v)));
// v=(p[2]-p[0]);
// vec.push_back(Line((p[2]+p[0])*0.5,Normal(v)));
// int m=HalfplaneIntersection(vec);
// double ans=PolygonArea(m,ansPoly);
// printf("%.3f\n",ans/(1.0*10000*10000));
Point p[];
void CC(Point *p)
{
for(int i=; i<maxn; i++)
{
p[i].x=;
p[i].y=;
}
}
int main()
{
// freopen("in.txt","r",stdin);
double a1,a2,a3,a4,a5,a6;
a5=(5.0**)/(**-);
a2=;
while(cin>>p[].x>>p[].y>>p[].x>>p[].y>>p[].x>>p[].y>>p[].x>>p[].y)
{
CC(ansPoly);
vector<Line>vec;
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(-0.5,-0.5),Point(-,)));
int sou_num=HalfplaneIntersection(vec);
a1=PolygonArea(sou_num,ansPoly);
// cout<<"a1:"<<a1<<endl;
// cout<<"sou_num:"<<sou_num<<endl;
// CC(ansPoly);
vec.clear();
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(-0.5,-0.5),Point(,)));
int west_num=HalfplaneIntersection(vec);
// cout<<ansPoly[3].y<<endl;
a4=PolygonArea(west_num,ansPoly);
// cout<<"a4:"<<a4<<endl;
// cout<<"west_num:"<<west_num<<endl;
CC(ansPoly);
vec.clear();
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(-0.5,0.5),Point(,)));
int nor_num=HalfplaneIntersection(vec);
a6=PolygonArea(nor_num,ansPoly);
// cout<<"a6:"<<a6<<endl;
// cout<<"nor_num:"<<nor_num<<endl;
CC(ansPoly);
vec.clear();
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(p[].x,p[].y),Point(p[].x-p[].x,p[].y-p[].y)));
vec.push_back(Line(Point(0.5,0.5),Point(,-)));
int east_num=HalfplaneIntersection(vec);
a3=PolygonArea(east_num,ansPoly);
// cout<<"a3:"<<a3<<endl;
// cout<<"east_num:"<<east_num<<endl;
long double ans1,ans2,ans3,ans4,ans5,ans6;
double ans;
// anss=(5.0*a1)/(5*5*5-1)+2*(5.0*a2)/(5*5*5-1)+3*(5.0*a3)/(5*5*5-1)+4*(5.0*a4)/(5*5*5-1)+a5*5.0+6*(5.0*a6)/(5*5*5-1);
ans1=(5.0*a1)/(**-);
// cout<<"ans1:"<<ans1<<endl;
ans2=(5.0*a2)/(**-);
// cout<<"ans2:"<<ans2<<endl;
ans3=*(5.0*a3)/(**-);
// cout<<"ans3:"<<ans3<<endl;
ans4=*(5.0*a4)/(**-);
// cout<<"ans4:"<<ans4<<endl;
ans5=*a5;
// cout<<"ans5:"<<ans5<<endl;
ans6=*(5.0*a6)/(**-);
// cout<<"ans6:"<<ans6<<endl;
ans=ans1+ans2+ans3+ans4+ans5+ans6;
printf("%.10lf\n",ans);
}
return ;
}