【题解】数三角（思维）

题目

题目描述

这是一个数三角的游戏。长度为$1$或$\sqrt2$的小木棍放在一个网格上。如图所示，有水平的，垂直的或对角的。对角放置的木棍可以交叉。

将木棍随意地放在网格上得到的图案可能不含三角形，也可能含一个或多个三角形。如下图所示，
$(a),(b),(c),(d)$和$(e)$分别含有$2,5,12,0,0$个三角形。你的任务是写一个程序数出一个图案中的三角形个数

输入格式

输入包括N+1行：

先输入图案中木棍的个数N。下面输入这N根木棍的位置，用两个网格坐标表示，这两个坐标分别为木棍两端的位置。网格大小不超过10´10，因此网格左下和右上的坐标分别为(0,0)和(9,9)。

输出格式

输入包括1行：

三角形的个数。

样例

样例输入

3
0 0 0 1
0 0 1 0
0 1 1 0

样例输出

1

题解

如果我们知道任意两点是否连通，判断三角形就会很简单：暴力枚举三个点，若三个点不共线且互相连通，即为三角形

现在主要就是如何知道两点连通

直观的想法就是用一个四维的$bool$数组$lt$,lt[x1][y1][x2][y2]表示点$(x1,y1)$和$(x2,y2)$是否连通，每输入一根火柴棍，就让这根火柴棍的两个端点连通，但现在有两个问题：

问题1.两根火柴棍在方格内交叉

如图：

在这张图中，6根火柴棍组成了8个三角形，但我们发现按上面的方法，会有4个小三角形被忽略：

就是形如上图的小三角形，因为内部交点没被计算，所以这种情况就会很难处理

方法是把一个小方格分成4个小方格：

这样在内部有交叉时，也可以轻松表示

当然这时的小三角形表示也就不在话下

OK,搞定了基本问题，让我们看看存边这一操作的代码实现

在同一列

首先执行将$1\times1$转化为$2\times2$的格子的操作：
$x1,y1,x2,y2$均$\times2$，方便后续计算，这时$x2=x1+2$,$y1=y2$

接下来是连边：

依次连接$(x1,y1),(x1+1,y1),(x2,y2)$,不要忘了反向连边

代码：

x1*=2,y1*=2,x2*=2,y2*=2;
if(x1==x2){
	if(y2>y1){
		lt[x1][y1][x1][y1+1]=true;
		lt[x1][y1+1][x1][y2]=true;
		lt[x1][y1+1][x1][y1]=true;
		lt[x1][y2][x1][y1+1]=true;
	}
	else{
		lt[x1][y1][x1][y1-1]=true;
		lt[x1][y1-1][x1][y2]=true;
		lt[x1][y1-1][x1][y1]=true;
		lt[x1][y2][x1][y1-1]=true;
	}
}

在同一行

与列同理