// OBčh2009 Day2 F : Voronoi Island #include #include #include using namespace std; typedef complex P; const double EPS = 1e-8; double cross(P a, P b){ return imag(conj(a)*b); } vector

convexCut(vector

g, P p, P q){ vector

res; int n = g.size(); for(int i=0;i -EPS) res.push_back(A); if(p1*p2 < -EPS) res.push_back(A+cross(q-p,q-A)/cross(q-p,B-A)*(B-A)); } return res; } double polygonArea(vector

g){ double res = 0.0; for(int i=0;i> n >> m, n){ vector

island, castle; for(int i=0;i> Ix >> Iy; island.push_back(P(Ix,Iy)); } for(int i=0;i> Cx >> Cy; castle.push_back(P(Cx,Cy)); } for(int i=0;i area = island; for(int j=0;jEPS) swap(q,mid); area = convexCut(area, q, mid); } printf("%.6lf\n", polygonArea(area)); } } }