当前位置：首页 > news >正文

UVa 527 The Partition of a Cake

news 2026/6/19 0:29:48

题目描述

题目要求计算一个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

输出

题目分析

本题的核心是模拟平面分割过程，计算每次添加一条直线后，区域数量的变化。

增量法

初始时，蛋糕是一个凸多边形（正方形），区域数为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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoubleEPSILON=1e-7;structpoint{doublex,y;booloperator==(constpoint&p)const{returnfabs(x-p.x)<=EPSILON&&fabs(y-p.y)<=EPSILON;}};structline{point a,b;boolcontains(point p){returnp.x>=min(a.x,b.x)&&p.x<=max(a.x,b.x)&&p.y>=min(a.y,b.y)&&p.y<=max(a.y,b.y);}};typedefvector<point>polygon;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 p=line1.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;}vector<polygon>halfPlaneIntersection(polygon pg,line cutline){polygon cutted;for(inti=0;i<pg.size();i++){point p1=pg[i];point p2=pg[(i+1)%pg.size()];cutted.push_back(p1);line edge=line{p1,p2};if(paralle(edge,cutline))continue;if(!collinear(cutline.a,cutline.b,p1)){point p3=intersection(edge,cutline);if(edge.contains(p3))cutted.push_back(p3);}}cutted.erase(unique(cutted.begin(),cutted.end()),cutted.end());if(cutted.size()>0&&cutted.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);}}vector<polygon>partitions;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;vector<point>square{point{0,0},point{1000,0},point{1000,1000},point{0,1000}};cin>>cases;for(intc=1;c<=cases;c++){if(c>1)cout<<'\n';vector<polygon>current,next;current.push_back(polygon{square});cin>>cuts;for(inti=1;i<=cuts;i++){cin>>x1>>y1>>x2>>y2;line cutline=line{point{x1,y1},point{x2,y2}};for(autopg:current){vector<polygon>partitions=halfPlaneIntersection(pg,cutline);for(autopartition:partitions)next.push_back(partition);}current.swap(next);next.clear();}cout<<current.size()<<'\n';}return0;}