本文共 4738 字，大约阅读时间需要 15 分钟。

题目描述

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

将木棍随意地放在网格上得到的图案可能不含三角形，也可能含一个或多个三角形。如下图所示

($a$),($b$),($c$),($d$)和($e$)分别含有$2$,$5$,$12$,$0$,$0$个三角形。你的任务是写一个程序数出一个图案中的三角形个数。

输入格式

输入文件$count.in$包括$N+1$行：

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

输出格式

输入文件$count.out$包括$1$行：
三角形的个数。

样例输入

30 0 0 10 0 1 00 1 1 0

样例输出

1

分析

总体来说，重要步骤为：
1.将输入的数转化为数组下标。
2.将一个格子分为四个小格子（因为可能会形成格子面积$1/4$的小三角形）。
3.$floyd$初始化。
4.$floyd$判断任意两点是否联通。
5.枚举三点，得出答案。

代码（有注释）

#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>using namespace std;const int MAXN = 25;int n, dp[MAXN][MAXN][MAXN][MAXN], x, y, x_, y_, ans;bool vis[MAXN][MAXN][MAXN][MAXN][MAXN][MAXN];int main() {   //	freopen("count.in", "r", stdin);//	freopen("count.out", "w", stdout);	int n;	scanf("%d", &n);	for(int i = 1; i <= n; i ++) {   		scanf("%d%d%d%d", &x, &y, &x_, &y_);		x = 20 - (x << 1); y = 20 - (y << 1); x_ = 20 - (x_ << 1); y_ = 20 - (y_ << 1);//切换成二维数组的下标+一个格子分为四个小格子!!!		if(x + y - x_ - y_ == 2) {   //纵向排列			if(x - x_ == 2) {   //(x, y)在(x_,y_)下方				dp[x_][y_][x_ + 1][y_] = 1;				dp[x_ + 1][y_][x_][y_] = 1;				dp[x_ + 1][y_][x][y] = 1;				dp[x][y][x_ + 1][y_] = 1;			}			else {   //(x, y)在(x_,y_)(x, y)在(x_, y_)右边				dp[x_][y_][x_][y_ + 1] = 1;				dp[x_][y_ + 1][x_][y_] = 1;				dp[x_][y_ + 1][x][y] = 1;				dp[x][y][x_][y_ + 1] = 1;			}		}		else if(x_ + y_ - x - y == 2) {   //横向排列			if(x_ - x == 2) {   //(x, y)在(x_, y_)上方				dp[x][y][x + 1][y] = 1;				dp[x + 1][y][x][y] = 1;				dp[x + 1][y][x_][y_] = 1;				dp[x_][y_][x + 1][y] = 1;			}			else {   //(x, y)在(x_, y_)左边				dp[x][y][x][y + 1] = 1;				dp[x][y + 1][x][y] = 1;				dp[x][y + 1][x_][y_] = 1;				dp[x_][y_][x][y + 1] = 1;			}		}		else if((x - y) == (x_ - y_)) {   //y=-x对角线 			if(x < x_) {   //(x, y)在(x_, y_)左上方				dp[x][y][x + 1][y + 1] = 1;				dp[x + 1][y + 1][x][y] = 1;				dp[x + 1][y + 1][x_][y_] = 1;				dp[x_][y_][x + 1][y + 1] = 1;			}			else {   //(x, y)在(x_, y_)右下方				dp[x_][y_][x_ + 1][y_ + 1] = 1;				dp[x_ + 1][y_ + 1][x_][y_] = 1;				dp[x_ + 1][y_ + 1][x][y] = 1;				dp[x][y][x_ + 1][y_ + 1] = 1;			}		}		else {   //y=x对角线 			if(x < x_) {   //(x, y)在(x_, y_)右上方				dp[x][y][x + 1][y - 1] = 1;				dp[x + 1][y - 1][x][y] = 1;				dp[x + 1][y - 1][x_][y_] = 1;				dp[x_][y_][x + 1][y - 1] = 1;			}			else {   //(x, y)在(x_, y_)左下方				dp[x_][y_][x_ + 1][y_ - 1] = 1;				dp[x_ + 1][y_ - 1][x_][y_] = 1;				dp[x_ + 1][y_ - 1][x][y] = 1;				dp[x][y][x_ + 1][y_ - 1] = 1;			}		}	}	for(int i = 2; i <= 20; i ++) {   //floyd思想 :先枚举中间点 ，判联通		for(int j = 2; j <= 20; j ++) {   			for(int k = 2; k <= 20; k ++) {   				for(int l = 2; l <= 20; l ++) {   					for(int o = 2; o <= 20; o ++) {   						for(int p = 2; p <= 20; p ++) {   							if(dp[k][l][i][j] && dp[o][p][i][j]) {   								if(((k == i) && (o == i)) || ((l == j) && (p == j)) || (((k + l) == (i + j)) && ((i + j) == (o + p)))) {   									dp[k][l][o][p] = dp[o][p][k][l] = 1; 								}								if(((k - l + 100) == (i - j + 100)) && ((i - j + 100) == (o - p + 100))) {   									dp[k][l][o][p] = dp[o][p][k][l] = 1;								}							}						}					}				}			}		}	}	for(int i = 2; i <= 20; i ++) {   		for(int j = 2; j <= 20; j ++) {   			for(int k = 2; k <= 20; k ++) {   				for(int l = 2; l <= 20; l ++) {   					for(int o = 2; o <= 20; o ++) {   						for(int p = 2; p <= 20; p ++) {   							if(vis[i][j][k][l][o][p] == 0) {   //枚举三角形三顶点，注意三点不能共线								if(i == k && j == l) continue;								if(i == o && j == p) continue;								if(k == o && l == p) continue;								if(i == k && k == o) continue;								if(j == l && l == p) continue;								if((i + j == k + l) && (k + l == o + p)) continue;								if((i - j + 100 == k - l + 100) && (k - l + 100 == o - p + 100)) continue;								if(dp[i][j][k][l] && dp[i][j][o][p] && dp[k][l][o][p]) {   				//					printf("%d %d %d %d %d %d\n", i, j, k, l, o, p);									ans ++;									vis[i][j][k][l][o][p] = 1;//标记，避免重复									vis[i][j][o][p][k][l] = 1;									vis[k][l][i][j][o][p] = 1;									vis[k][l][o][p][i][j] = 1;									vis[o][p][i][j][k][l] = 1;									vis[o][p][k][l][i][j] = 1;								}										}						}					}				}			}		}	}	printf("%d", ans);	return 0;}

补充

做复杂了！
1.后来我想了一想，发现自己好傻。。。$17$~$73$行的代码可以优化成：

int midx = (x + x_) >> 1, midy = (y + y_) >> 1;dp[x][y][midx][midy] = 1;dp[midx][midy][x][y] = 1;dp[midx][midy][x_][y_] = 1;dp[x_][y_][midx][midy] = 1;

显然，我不用解释了。
2.判断两点是否相连时，可以改成：$K_{l,mid}!=K_{mid,r}$即可。（$K$为斜率）