题意分析

1. 本题是关于“挑棍”游戏中小棍连接关系的判断问题。
2. 输入为多个测试用例，每个测试用例包含小棍数量 n，以及每根小棍的两个端点坐标 (x1, y1) 和 (x2, y2)。
3. 对于每个测试用例，除最后一行 a = 0 且 b = 0 外，每行输入两个小棍编号 a 和 b，需判断小棍 a 和 b 是否相连。
4. 相连的定义为：相接触即相连，且两根小棍可以通过其他相连的小棍间接相连，一根小棍与其自身视为相连。

解题思路

1. 定义基本数据结构和操作：
   • 定义 node 结构体表示二维平面上的点，重载了加法、减法、数乘、点积、叉积等操作，方便后续进行几何计算。
   • 定义 add 函数用于处理浮点数加法，避免精度问题。
2. 几何判断函数：
   • on_seg 函数用于判断一个点是否在线段上。通过判断点与线段两端点的叉积是否为 0 且点积是否小于等于 0 来确定。
   • intersection 函数用于计算两条直线的交点。通过特定公式计算，该公式能处理斜率不存在的情况。
3. 构建图的邻接矩阵：
   • 初始化邻接矩阵 g，表示小棍之间的连接关系，初始时除自身与自身相连，其他都不相连。
   • 对于每两根小棍，判断它们是否平行（通过叉积判断）：
     • 若平行，则通过判断端点是否在另一条线段上来确定连接关系。
     • 若不平行，则计算交点，并判断交点是否在两条线段上确定连接关系。
4. 传递闭包算法：
   • 使用类似Floyd算法的传递闭包操作，更新邻接矩阵，确定所有小棍之间的间接连接关系。
5. 输出结果：
   • 根据邻接矩阵 g 判断输入的小棍对 a 和 b 是否相连，输出相应结果。

复杂度分析

1. 时间复杂度：
   • 初始化邻接矩阵和判断小棍连接关系的部分，时间复杂度为 $O(n^2)$，因为有两层循环遍历每对小棍，而判断相交等操作的时间复杂度相对较低，可视为常数级。
   • 传递闭包操作的时间复杂度为 $O(n^3)$，因为有三层循环。
   • 总体时间复杂度为 $O(n^3)$，由于 $n < 13$，实际运行时间较短。
2. 空间复杂度：
   • 主要空间消耗在邻接矩阵 g 上，大小为 $O(n^2)$。
   • 还存储了小棍端点坐标等，总体空间复杂度为 $O(n^2)$。

代码实现

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const double eps=1e-10;
int n;
double add(double a,double b)
{
	if(abs(a+b)<eps*(abs(a)+abs(b)))  return 0;
	return a+b;
}
struct node
{
	double x,y;
	node(){
	}
	node(double x,double y):x(x),y(y){
	}
	node operator+(node p)
	{
		return node(add(x,p.x),add(y,p.y));
	}
	node operator-(node p)
	{
		return node(add(x,-p.x),add(y,-p.y));
	}
	node operator*(double d)
	{
		return(node(d*x,d*y));
	}
	double dot(node p)
	{
		return add(x*p.x,y*p.y);
	}
	double det(node p)
	{
		return add(x*p.y,-y*p.x);
	} 
};
node p[20],q[20];
bool g[40][40]; 
int on_seg(node p,node q,node r)//这一段处理很不错,判断坐标r在不在线段p-q上 
{
	if(((p-r).det(q-r))==0 && (p-r).dot(q-r)<=0)
		return 1;
	return 0;
}
node intersection(node p1,node p2,node q1,node q2)//计算p1-p2和q1-q2直线交点 
{
	return p1+(p2-p1)*((q2-q1).det(q1-p1)/(q2-q1).det(p2-p1));//这种计算方法挺不错，可以处理斜率不存在的情况！ 
}
void solve()
{
	memset(g,0,sizeof(g));
	for(int i=0;i<n;i++)
	{
		g[i][i]=1;
		for(int j=0;j<i;j++)
		{
			if((p[i]-q[i]).det(p[j]-q[j])==0)//相交公式算不了平行时的情况 
			{//平行		 
				g[i][j]=g[j][i]=on_seg(p[i],q[i],p[j])
				||on_seg(p[i],q[i],q[j])
				||on_seg(p[j],q[j],p[i])
				||on_seg(p[j],q[j],q[i]);
			}else
			{
				node tp=intersection(p[i],q[i],p[j],q[j]);
				//if(i==3&&j==0) printf("%(%lf %lf) %lf %lf*\n",p[i].x,p[i].y,tp.x,tp.y);
				g[i][j]=g[j][i]=on_seg(p[i],q[i],tp)&&on_seg(p[j],q[j],tp);
			}
		}
	}
	for(int k=0;k<n;k++)
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				g[i][j] |= g[i][k]&&g[k][j];
			}
		}
	}
}
int main()
{
	//freopen("t.txt","r",stdin);
	int a,b;
	while(~scanf("%d",&n)&&n)
	{
		for(int i=0;i<n;i++)
		{
			scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&q[i].x,&q[i].y);		
		}
		solve();
		while(~scanf("%d%d",&a,&b))
		{
			if(a==0&&b==0) break;
			if(g[a-1][b-1])
				printf("CONNECTED\n");
			else
				printf("NOT CONNECTED\n");
		}
	}
	return 0;
}