UVa 273 Jack Straws

题目分析本题的题目背景源自一种名为 “Jack Straws\texttt{Jack Straws}Jack Straws” 的游戏玩家需要从桌上一堆杂乱摆放的塑料或木质 “稻草” 中逐根取出而不扰动其他稻草。本题不关心游戏过程只关心一个问题给定若干根稻草视为二维平面上的线段以及多组询问(a,b)(a, b)(a,b)判断稻草aaa和稻草bbb是否 “连通”。“连通” 的定义包含两个层面直接连通两根稻草在平面上有公共点即线段相交此时称它们直接相连。间接连通如果稻草aaa与稻草ccc直接相连且稻草ccc与稻草bbb直接相连则aaa与bbb间接连通。连通关系具有传递性。此外一根稻草与自身视为连通。输入格式较为特殊有多组测试数据每组数据以nnn开头1n131 n 131n13随后nnn行每行给出四个正整数x1,y1,x2,y2x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​表示一根稻草的两个端点坐标。接着是多行询问每行包含两个正整数a,ba, ba,b以0 0作为询问结束标志。输出时每组测试数据之间需要用空行分隔。解题思路本题的核心可以分解为三个步骤判断任意两根稻草是否直接相连线段相交判断。根据直接相连关系计算所有稻草之间的连通性传递闭包。对每个询问O(1)O(1)O(1)时间输出连通性结果。第一步线段相交判断两根稻草在平面上均为线段我们需要判断它们是否相交。线段相交的情况包括规范相交两条线段在内部非端点相交。非规范相交相交于端点或一条线段端点在另一条线段上。由于题目保证没有零长度稻草我们不需要处理退化为点的情况。判断线段相交的常用方法是跨立实验结合矩形快速排斥。设线段ABABAB和CDCDCD则快速排斥两个线段的外接矩形必须有重叠否则不可能相交。这一步可以提前过滤掉明显不相交的情况。在实现中快速排斥通常被包含在点是否在矩形内的判断中。跨立实验对于线段ABABAB和CDCDCD要求点CCC和点DDD位于直线ABABAB的两侧且点AAA和点BBB位于直线CDCDCD的两侧。用叉积判断方向d1AB→×AC→d_1 \overrightarrow{AB} \times \overrightarrow{AC}d1​AB×ACd2AB→×AD→d_2 \overrightarrow{AB} \times \overrightarrow{AD}d2​AB×ADd3CD→×CA→d_3 \overrightarrow{CD} \times \overrightarrow{CA}d3​CD×CAd4CD→×CB→d_4 \overrightarrow{CD} \times \overrightarrow{CB}d4​CD×CB如果d1⋅d20d_1 \cdot d_2 0d1​⋅d2​0且d3⋅d40d_3 \cdot d_4 0d3​⋅d4​0则规范相交。端点相交处理如果某个叉积为零说明对应点在另一条线段所在直线上此时还需用点是否在线段上判断即点在矩形范围内。这是处理非规范相交的关键。为什么选择这种方案n13n 13n13非常小即使对所有稻草对进行O(n2)O(n^2)O(n2)的相交检测也毫无压力。线段相交判断逻辑清晰且能正确处理端点接触的情况满足题目 “触碰即连通” 的要求。第二步传递闭包计算得到直接相连关系后我们需要求出连通关系的传递闭包。由于n≤12n \le 12n≤12可以用Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法的变种将连通性视作n×nn \times nn×n的布尔矩阵connected[i][j]。初始化若线段iii与线段jjj直接相交包括ijijij则connected[i][j] true。三重循环for k in [0, n-1]for i in [0, n-1]for j in [0, n-1]若connected[i][k] connected[k][j]成立则connected[i][j] true。时间复杂度为O(n3)O(n^3)O(n3)n≤12n \le 12n≤12时完全可接受。为什么不直接DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS虽然nnn很小但询问次数未知。预处理出所有对之间的连通性后每个询问只需O(1)O(1)O(1)输出效率更高。第三步处理询问与输出格式输入询问时连续读取a,ba, ba,b直到遇到0 0。输出时注意每组测试数据之间有一个空行。第一个测试数据前不输出空行。代码实现// Jack Straws// UVa ID: 273// Verdict: Accepted// Submission Date: 2016-05-15// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 点结构体structpoint{intx,y;};// 线段结构体structsegment{point start,end;};// 判断点 p 是否在线段 ab 的包围盒内boolpointInBox(point p,point a,point b){return((p.xmin(a.x,b.x))(p.xmax(a.x,b.x))(p.ymin(a.y,b.y))(p.ymax(a.y,b.y)));}// 计算叉积(b - a) × (c - a)doubledirection(point a,point b,point c){return(b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x);}// 判断两条线段是否相交包括端点接触boolsegmentsIntersect(segment a,segment b){doubled1,d2,d3,d4;d1direction(a.start,a.end,b.start);d2direction(a.start,a.end,b.end);d3direction(b.start,b.end,a.start);d4direction(b.start,b.end,a.end);// 规范相交互相跨立if((d1*d20)(d3*d40))returntrue;// 非规范相交端点重合或端点在另一线段上if(d10pointInBox(b.start,a.start,a.end))returntrue;if(d20pointInBox(b.end,a.start,a.end))returntrue;if(d30pointInBox(a.start,b.start,b.end))returntrue;if(d40pointInBox(a.end,b.start,b.end))returntrue;returnfalse;}intmain(intargc,char*argv[]){boolfirsttrue;// 控制输出空行intcases;cincases;while(cases--){intn,x1,y1,x2,y2;cinn;// 存储所有稻草vectorsegmentsegments;for(inti1;in;i){cinx1y1x2y2;segments.push_back((segment){(point){x1,y1},(point){x2,y2}});}// 初始化连通矩阵boolconnected[13][13];for(inti0;in;i)for(intj0;jn;j)connected[i][j]false;// 根据线段相交关系填充直接连通性for(inti0;isegments.size();i)for(intj0;jsegments.size();j)if(segmentsIntersect(segments[i],segments[j]))connected[i][j]true;// Floyd-Warshall 求传递闭包for(intk0;kn;k)for(inti0;in;i)for(intj0;jn;j)if(connected[i][k]connected[k][j])connected[i][j]true;// 控制两组数据之间的空行if(first)firstfalse;elsecoutendl;// 处理询问inta,b;while(cinab,ab)cout(connected[a-1][b-1]?CONNECTED:NOT CONNECTED)endl;}return0;}总结本题是一道典型的计算几何与图论结合的题目。核心难点在于正确判断两条线段是否相交特别是端点接触的情况。由于数据规模极小我们可以直接使用O(n3)O(n^3)O(n3)的Floyd-Warshall\texttt{Floyd-Warshall}Floyd-Warshall算法计算传递闭包从而高效地回答所有连通性询问。解题时注意输出格式特别是多组数据之间的空行处理。