UVa 273 Jack Straws

题目分析

本题的题目背景源自一种名为 “Jack Straws\texttt{Jack Straws}Jack Straws” 的游戏，玩家需要从桌上一堆杂乱摆放的塑料或木质 “稻草” 中逐根取出，而不扰动其他稻草。本题不关心游戏过程，只关心一个问题：给定若干根稻草（视为二维平面上的线段），以及多组询问(a,b)(a, b)(a,b)，判断稻草aaa和稻草bbb是否 “连通”。

“连通” 的定义包含两个层面：

1. 直接连通：两根稻草在平面上有公共点（即线段相交），此时称它们直接相连。
2. 间接连通：如果稻草aaa与稻草ccc直接相连，且稻草ccc与稻草bbb直接相连，则aaa与bbb间接连通。连通关系具有传递性。

此外，一根稻草与自身视为连通。

输入格式较为特殊：有多组测试数据，每组数据以nnn开头（1<n<131 < n < 131<n<13），随后nnn行每行给出四个正整数x1,y1,x2,y2x_1, y_1, x_2, y_2x1​,y1​,x2​,y2​，表示一根稻草的两个端点坐标。接着是多行询问，每行包含两个正整数a,ba, ba,b，以0 0作为询问结束标志。输出时，每组测试数据之间需要用空行分隔。

解题思路

本题的核心可以分解为三个步骤：

1. 判断任意两根稻草是否直接相连（线段相交判断）。
2. 根据直接相连关系，计算所有稻草之间的连通性（传递闭包）。
3. 对每个询问，O(1)O(1)O(1)时间输出连通性结果。

第一步：线段相交判断

两根稻草在平面上均为线段，我们需要判断它们是否相交。线段相交的情况包括：

• 规范相交：两条线段在内部（非端点）相交。
• 非规范相交：相交于端点，或一条线段端点在另一条线段上。

由于题目保证没有零长度稻草，我们不需要处理退化为点的情况。

判断线段相交的常用方法是跨立实验结合矩形快速排斥。设线段ABABAB和CDCDCD，则：

1. 快速排斥：两个线段的外接矩形必须有重叠，否则不可能相交。这一步可以提前过滤掉明显不相交的情况。在实现中，快速排斥通常被包含在点是否在矩形内的判断中。

2. 跨立实验：对于线段ABABAB和CDCDCD，要求点CCC和点DDD位于直线ABABAB的两侧，且点AAA和点BBB位于直线CDCDCD的两侧。用叉积判断方向：

   • d1=AB→×AC→d_1 = \overrightarrow{AB} \times \overrightarrow{AC}d1​=AB×AC
   • d2=AB→×AD→d_2 = \overrightarrow{AB} \times \overrightarrow{AD}d2​=AB×AD
   • d3=CD→×CA→d_3 = \overrightarrow{CD} \times \overrightarrow{CA}d3​=CD×CA
   • d4=CD→×CB→d_4 = \overrightarrow{CD} \times \overrightarrow{CB}d4​=CD×CB

   如果d1⋅d2<0d_1 \cdot d_2 < 0d1​⋅d2​<0且d3⋅d4<0d_3 \cdot d_4 < 0d3​⋅d4​<0，则规范相交。

3. 端点相交处理：如果某个叉积为零，说明对应点在另一条线段所在直线上，此时还需用点是否在线段上判断（即点在矩形范围内）。这是处理非规范相交的关键。

为什么选择这种方案？
n<13n < 13n<13非常小，即使对所有稻草对进行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直接相交（包括i=ji=ji=j），则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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;// 点结构体structpoint{intx,y;};// 线段结构体structsegment{point start,end;};// 判断点 p 是否在线段 ab 的包围盒内boolpointInBox(point p,point a,point b){return((p.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)));}// 计算叉积：(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;d1=direction(a.start,a.end,b.start);d2=direction(a.start,a.end,b.end);d3=direction(b.start,b.end,a.start);d4=direction(b.start,b.end,a.end);// 规范相交：互相跨立if((d1*d2<0)&&(d3*d4<0))returntrue;// 非规范相交：端点重合或端点在另一线段上if(d1==0&&pointInBox(b.start,a.start,a.end))returntrue;if(d2==0&&pointInBox(b.end,a.start,a.end))returntrue;if(d3==0&&pointInBox(a.start,b.start,b.end))returntrue;if(d4==0&&pointInBox(a.end,b.start,b.end))returntrue;returnfalse;}intmain(intargc,char*argv[]){boolfirst=true;// 控制输出空行intcases;cin>>cases;while(cases--){intn,x1,y1,x2,y2;cin>>n;// 存储所有稻草vector<segment>segments;for(inti=1;i<=n;i++){cin>>x1>>y1>>x2>>y2;segments.push_back((segment){(point){x1,y1},(point){x2,y2}});}// 初始化连通矩阵boolconnected[13][13];for(inti=0;i<n;i++)for(intj=0;j<n;j++)connected[i][j]=false;// 根据线段相交关系填充直接连通性for(inti=0;i<segments.size();i++)for(intj=0;j<segments.size();j++)if(segmentsIntersect(segments[i],segments[j]))connected[i][j]=true;// Floyd-Warshall 求传递闭包for(intk=0;k<n;k++)for(inti=0;i<n;i++)for(intj=0;j<n;j++)if(connected[i][k]&&connected[k][j])connected[i][j]=true;// 控制两组数据之间的空行if(first)first=false;elsecout<<endl;// 处理询问inta,b;while(cin>>a>>b,a&&b)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算法计算传递闭包，从而高效地回答所有连通性询问。解题时注意输出格式，特别是多组数据之间的空行处理。