题目描述题目要求计算一个1000×10001000 \times 10001000×1000的正方形蛋糕被若干条直线切割后被分成的区域数量。每条切割线由它与蛋糕边界的两个交点确定保证两个交点都在边界上。切割线数量不超过888。切割后每个区域的最小边长不小于111。输入格式第一行一个整数MMM表示数据集的个数后面跟一个空行。每个数据集的第一行是一个整数nnn表示切割线的数量。接下来nnn行每行四个整数(x1,y1,x2,y2)(x_1, y_1, x_2, y_2)(x1​,y1​,x2​,y2​)表示一条切割线与蛋糕边界的两个交点。两个连续数据集之间由一个空行分隔。输出格式对于每个数据集输出一行一个整数表示蛋糕被分割成的区域数量。两个连续数据集的输出之间由一个空行分隔。样例输入1 3 0 0 1000 1000 500 0 500 1000 0 500 1000 500输出6题目分析本题的核心是模拟平面分割过程计算每次添加一条直线后区域数量的变化。增量法初始时蛋糕是一个凸多边形正方形区域数为111。每次添加一条直线该直线将穿过一些现有区域并将每个穿过的区域一分为二。因此新增的区域数量等于该直线穿过的区域数量。而一条直线穿过的区域数量等于它与已有直线的交点数在蛋糕边界内的交点加111。更直接的方法是使用平面图的欧拉公式但这里n≤8n \le 8n≤8可以直接模拟多边形分割。模拟分割将蛋糕初始化为一个多边形正方形。对于每条切割线将当前所有多边形与切割线进行半平面交得到两个新多边形切割线两侧。将所有多边形收集起来继续下一条切割线。最终多边形的个数即为区域数。半平面交给定一个凸多边形和一条直线直线将多边形分为左右两部分根据方向。分别取两侧的半平面与多边形求交得到两个新的凸多边形。复杂度分析每次切割最多使多边形数量翻倍最终多边形数量O(2n)O(2^n)O(2n)n≤8n \le 8n≤8可接受。代码实现// The partition of a cake// UVa ID: 527// Verdict: Accepted// Submission Date: 2017-05-09// UVa Run Time: 0.080s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;constdoubleEPSILON1e-7;structpoint{doublex,y;booloperator(constpointp)const{returnfabs(x-p.x)EPSILONfabs(y-p.y)EPSILON;}};structline{point a,b;boolcontains(point p){returnp.xmin(a.x,b.x)p.xmax(a.x,b.x)p.ymin(a.y,b.y)p.ymax(a.y,b.y);}};typedefvectorpointpolygon;doublecrossProduct(point p1,point p2,point p3){return(p3.x-p1.x)*(p2.y-p1.y)-(p2.x-p1.x)*(p3.y-p1.y);}boolcw(point p1,point p2,point p3){returncrossProduct(p1,p2,p3)EPSILON;}boolcollinear(point p1,point p2,point p3){returnfabs(crossProduct(p1,p2,p3))EPSILON;}boolparalle(line line1,line line2){returnfabs((line1.a.x-line1.b.x)*(line2.a.y-line2.b.y)-(line2.a.x-line2.b.x)*(line1.a.y-line1.b.y))EPSILON;}pointintersection(line line1,line line2){point pline1.a;doublescale((line1.a.x-line2.a.x)*(line2.a.y-line2.b.y)-(line1.a.y-line2.a.y)*(line2.a.x-line2.b.x))/((line1.a.x-line1.b.x)*(line2.a.y-line2.b.y)-(line1.a.y-line1.b.y)*(line2.a.x-line2.b.x));p.x(line1.b.x-line1.a.x)*scale;p.y(line1.b.y-line1.a.y)*scale;returnp;}vectorpolygonhalfPlaneIntersection(polygon pg,line cutline){polygon cutted;for(inti0;ipg.size();i){point p1pg[i];point p2pg[(i1)%pg.size()];cutted.push_back(p1);line edgeline{p1,p2};if(paralle(edge,cutline))continue;if(!collinear(cutline.a,cutline.b,p1)){point p3intersection(edge,cutline);if(edge.contains(p3))cutted.push_back(p3);}}cutted.erase(unique(cutted.begin(),cutted.end()),cutted.end());if(cutted.size()0cutted.front()cutted.back())cutted.pop_back();polygon leftHalf,rightHalf;for(autov:cutted){if(collinear(cutline.a,cutline.b,v)){leftHalf.push_back(v);rightHalf.push_back(v);}else{if(cw(cutline.a,cutline.b,v))rightHalf.push_back(v);elseleftHalf.push_back(v);}}vectorpolygonpartitions;if(leftHalf.size()3)partitions.push_back(leftHalf);if(rightHalf.size()3)partitions.push_back(rightHalf);returnpartitions;}intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intcases,cuts;doublex1,y1,x2,y2;vectorpointsquare{point{0,0},point{1000,0},point{1000,1000},point{0,1000}};cincases;for(intc1;ccases;c){if(c1)cout\n;vectorpolygoncurrent,next;current.push_back(polygon{square});cincuts;for(inti1;icuts;i){cinx1y1x2y2;line cutlineline{point{x1,y1},point{x2,y2}};for(autopg:current){vectorpolygonpartitionshalfPlaneIntersection(pg,cutline);for(autopartition:partitions)next.push_back(partition);}current.swap(next);next.clear();}coutcurrent.size()\n;}return0;}