题目描述
这是一个数三角的游戏。长度为1或SQRT(2)的小木棍放在一个网格上。如图所示，有水平的，垂直的或对角的。对角放置的木棍可以交叉。
将木棍随意地放在网格上得到的图案可能不含三角形，也可能含一个或多个三角形。如下图所示，
(a),(b),©,(d)和(e)分别含有2,5,12,0,0个三角形。你的任务是写一个程序数出一个图案中的三角形个数。。cpp
输入格式
输入文件count.in包括N+1行：
先输入图案中木棍的个数N。下面输入这N根木棍的位置，用两个网格坐标表示，这两个坐标分别为木棍两端的位置。网格大小不超过10´10，因此网格左下和右上的坐标分别为(0,0)和(9,9)。
输出格式
输入文件count.out包括1行：
三角形的个数。
样例
样例输入
3
0 0 0 1
0 0 1 0
0 1 1 0
样例输出
1
分析
我在考试时的思路是定义一个 三维数组 G[x][y][state]
表示取火柴棒较上的端点的位置， state表示摆放的状态 ： 1 -> 向左倾斜 2 -> 向右倾斜 3 -> 垂直于网格线 4 -> 平行于网格线
但我在实现的过程中发现了问题，如果在端点离得比较远的时候，枚举会很浪费时间，并且能够构成三角形的组合非常多，不易写出代码，调试程序会变得非常的麻烦。
考试后看了 LJS的代码后又重新理了一下思路：
此题的步骤大致分成三个板块 ：
- 预处理
- 处理连通性 -> Floyd
- 判断是否构成三角形
预处理
1.将输入坐标依次扩大两倍
如下图：
这样的话就可以判断如小图中对角线交叉，可以使得对对角线的交点处于网格上。
在一次判断两点之间的关系
2.标记所连接的线段是对角线还是在网格线上面。
参考代码如下(比较累赘)：
for(int i = 1;i <= n; i++) {
int a1, a2, a3, a4;
scanf("%d %d %d %d", &a1, &a2, &a3, &a4);
a1 *= 2, a2 *= 2, a3 *= 2, a4 *= 2;
if (a3 + a4 - a1 - a2 == 2) { //在网格线的直边上面
if (a2 == a4) {//竖
map[a1 + 1][a2][a3][a2] = 1;
map[a3][a2][a1 + 1][a2] = 1;
map[a1 + 1][a2][a1][a2] = 1;
map[a1][a2][a1 + 1][a2] = 1;
}
if (a1 == a3) {//横
map[a1][a2 + 1][a1][a4] = 1;
map[a1][a4][a1][a2 + 1] = 1;
map[a1][a2 + 1][a1][a2] = 1;
map[a1][a2][a1][a2 + 1] = 1;
}
}
if (a1 + a2 - a3 - a4 == 2) {//反向
if (a2 == a4) {
map[a1][a2][a3 + 1][a2] = 1;
map[a3 + 1][a2][a1][a2] = 1;
map[a3][a2][a3 + 1][a2] = 1;
map[a3][a2][a3 + 1][a2] = 1;
}
if (a1 == a3) {
map[a1][a2][a1][a4 + 1] = 1;
map[a1][a4 + 1][a1][a2] = 1;
map[a1][a4 + 1][a1][a4] = 1;
map[a1][a4][a1][a4 + 1] = 1;
}
}
if (a1 + a2 - a3 - a4 == 4) {//在对角线上面
map[a3 + 1][a4 + 1][a1][a2] = 1;
map[a1][a2][a3 + 1][a4 + 1] = 1;
map[a3][a4][a3 + 1][a4 + 1] = 1;
map[a3 + 1][a4 + 1][a3][a4] = 1;
}
if (a3 + a4 - a1 - a2 == 4) {
map[a1 + 1][a2 + 1][a3][a4] = 1;
map[a3][a4][a1 + 1][a2 + 1] = 1;
map[a1][a2][a1 + 1][a2 + 1] = 1;
map[a1 + 1][a2 + 1][a1][a2] = 1;
}
if (a1 + a2 == a3 + a4) {
map[a1][a2][(a1 + a3) / 2][(a2 + a4) / 2] = 1;
map[(a1 + a3) / 2][(a2 + a4) / 2][a1][a2] = 1;
map[a3][a4][(a1 + a3) / 2][(a2 + a4) / 2] = 1;
map[(a1 + a3) / 2][(a2 + a4) / 2][a3][a4] = 1;
}
map[a1][a2][a3][a4] = 1;//将已经给出的两点连在一起
map[a3][a4][a1][a2] = 1;
}
求出连通性
参考 Floyd算法的思想：
枚举中转点 i与和它相连接的另外两个不同于中转点且没有连接的节点 z, j，判断两点之间的可连性（三点共线），如果可以，就将其连接。
可连性判断：
(z1−i1)∗(j−i)−(j1−i1)∗(z−i)==0
for (int i = 0; i <= 18; i++) {
for (int j = 0; j <= 18; j++) {
for (int z = 0; z <= 18; z++) {
for (int i1 = 0; i1 <= 18; i1++) {
for (int j1 = 0; j1 <= 18; j1++) {
for (int z1 = 0; z1 <= 18; z1++) {
if (map[i][i1][j][j1] == 1 && map[i][i1][z][z1] == 1
&& !(i == j && i1 == j1) && !(i == z && i1 == z1)
&& (z1 - i1) * (j - i) - (j1 - i1) * (z - i) == 0
&& map[j][j1][z][z1] == 0 && map[z][z1][j][j1] == 0) {
map[j][j1][z][z1] = 1;
map[z][z1][j][j1] = 1;
}
}
}
}
}
}
}
判断是否构成三角形
判断方式：暴力枚举三角形的三个端点，如果三点之间能够相连，那么能够组成三角形，就 ans++。
在输出时应该注意要将 ans/6，因为在枚举三个端点会出现重复，根据乘法原理可知， ans的枚举将会重复 3∗2∗1次。
for (int i = 0; i <= 18; i++) {
for (int j = 0; j <= 18; j++) {
for (int z = 0; z <= 18; z++) {
for (int i1 = 0; i1 <= 18; i1++) {
for (int j1 = 0; j1 <= 18; j1++) {
for (int z1 = 0; z1 <= 18; z1++) {
if (map[i][i1][j][j1] == 1 && map[i][i1][z][z1] == 1
&& map[j][j1][z][z1] == 1
&& !(i == j && i1 == j1) && !(i == z && i1 == z1)
&& !(j == z && j1 == z1)
&& (z1 - i1) * (j - i) - (j1 - i1) * (z - i) != 0) {
ans++;
}
}
}
}
}
}
}
ans /= (3 * 2 * 1);
完整代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 35;
bool map[MAXN][MAXN][MAXN][MAXN];
int n, ans;
int main() {
scanf("%d", &n);
for(int i = 1;i <= n; i++) {
int a1, a2, a3, a4;
scanf("%d %d %d %d", &a1, &a2, &a3, &a4);
a1 *= 2, a2 *= 2, a3 *= 2, a4 *= 2;
if (a3 + a4 - a1 - a2 == 2) { //在网格线的直边上面
if (a2 == a4) {//竖
map[a1 + 1][a2][a3][a2] = 1;
map[a3][a2][a1 + 1][a2] = 1;
map[a1 + 1][a2][a1][a2] = 1;
map[a1][a2][a1 + 1][a2] = 1;
}
if (a1 == a3) {//横
map[a1][a2 + 1][a1][a4] = 1;
map[a1][a4][a1][a2 + 1] = 1;
map[a1][a2 + 1][a1][a2] = 1;
map[a1][a2][a1][a2 + 1] = 1;
}
}
if (a1 + a2 - a3 - a4 == 2) {//反向
if (a2 == a4) {
map[a1][a2][a3 + 1][a2] = 1;
map[a3 + 1][a2][a1][a2] = 1;
map[a3][a2][a3 + 1][a2] = 1;
map[a3][a2][a3 + 1][a2] = 1;
}
if (a1 == a3) {
map[a1][a2][a1][a4 + 1] = 1;
map[a1][a4 + 1][a1][a2] = 1;
map[a1][a4 + 1][a1][a4] = 1;
map[a1][a4][a1][a4 + 1] = 1;
}
}
if (a1 + a2 - a3 - a4 == 4) {//在对角线上面
map[a3 + 1][a4 + 1][a1][a2] = 1;
map[a1][a2][a3 + 1][a4 + 1] = 1;
map[a3][a4][a3 + 1][a4 + 1] = 1;
map[a3 + 1][a4 + 1][a3][a4] = 1;
}
if (a3 + a4 - a1 - a2 == 4) {
map[a1 + 1][a2 + 1][a3][a4] = 1;
map[a3][a4][a1 + 1][a2 + 1] = 1;
map[a1][a2][a1 + 1][a2 + 1] = 1;
map[a1 + 1][a2 + 1][a1][a2] = 1;
}
if (a1 + a2 == a3 + a4) {
map[a1][a2][(a1 + a3) / 2][(a2 + a4) / 2] = 1;
map[(a1 + a3) / 2][(a2 + a4) / 2][a1][a2] = 1;
map[a3][a4][(a1 + a3) / 2][(a2 + a4) / 2] = 1;
map[(a1 + a3) / 2][(a2 + a4) / 2][a3][a4] = 1;
}
map[a1][a2][a3][a4] = 1;//将已经给出的两点连在一起
map[a3][a4][a1][a2] = 1;
}
for (int i = 0; i <= 18; i++) {
for (int j = 0; j <= 18; j++) {
for (int z = 0; z <= 18; z++) {
for (int i1 = 0; i1 <= 18; i1++) {
for (int j1 = 0; j1 <= 18; j1++) {
for (int z1 = 0; z1 <= 18; z1++) {
if (map[i][i1][j][j1] == 1 && map[i][i1][z][z1] == 1 && !(i == j && i1 == j1) && !(i == z && i1 == z1) && (z1 - i1) * (j - i) - (j1 - i1) * (z - i) == 0 && map[j][j1][z][z1] == 0 &&
map[z][z1][j][j1] == 0) {
map[j][j1][z][z1] = 1;
map[z][z1][j][j1] = 1;
}
}
}
}
}
}
}
for (int i = 0; i <= 18; i++) {
for (int j = 0; j <= 18; j++) {
for (int z = 0; z <= 18; z++) {
for (int i1 = 0; i1 <= 18; i1++) {
for (int j1 = 0; j1 <= 18; j1++) {
for (int z1 = 0; z1 <= 18; z1++) {
if (map[i][i1][j][j1] == 1 && map[i][i1][z][z1] == 1 && map[j][j1][z][z1] == 1 &&
!(i == j && i1 == j1) && !(i == z && i1 == z1) && !(j == z && j1 == z1) &&
(z1 - i1) * (j - i) - (j1 - i1) * (z - i) != 0) {
ans++;
}
}
}
}
}
}
}
ans /= (3 * 2 * 1);
printf("%d\n", ans);
return 0;
}
京公网安备 11010502036488号