「Solution」数三角

Posted on Edited on

@TOC

题目描述

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

在这里插入图片描述

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

在这里插入图片描述

(a),(b),(c),(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.标记所连接的线段是对角线还是在网格线上面。
    参考代码如下(比较累赘)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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$次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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);

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#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;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」