QOJ.ac

QOJ

Limite de temps : 2 s Limite de mémoire : 1024 MB Points totaux : 100

#3205. 球与针

Statistiques

Joana Vasconcelos 是一位葡萄牙艺术家,她经常在创作中使用日常物品,例如电熨斗或塑料餐具。她激发了 Ana 的灵感,Ana 想要用直的织针和毛线球制作天花板悬挂雕塑。出于安全考虑,每根织针的两端都会有一个毛线球。织针的颜色、长度和粗细各不相同(以允许织针之间相互交叉)。

雕塑将展示在房间的角落里,这些角落提供了一个三维笛卡尔坐标系,天花板上有许多灯。雕塑的设计基于织针所插入的毛线球的中心坐标。也就是说,每根织针 $N$ 由两组不同的三元组表示:$N = \{(x, y, z), (x', y', z')\}$。

Ana 不喜欢“闭合链”。一条“真闭合链”是 $k$ 根不同织针的序列 $N_1, N_2, \dots, N_k$(其中 $k \ge 3$),满足: * $N_1 = \{(x_1, y_1, z_1), (x_2, y_2, z_2)\}, N_2 = \{(x_2, y_2, z_2), (x_3, y_3, z_3)\}, \dots, N_k = \{(x_k, y_k, z_k), (x_{k+1}, y_{k+1}, z_{k+1})\}$,且 $(x_{k+1}, y_{k+1}, z_{k+1}) = (x_1, y_1, z_1)$。

但她对闭合链的厌恶程度非常高,以至于她同样不喜欢雕塑在地面上的投影形成“地面闭合链”。给定任意织针 $N = \{(x, y, z), (x', y', z')\}$,令 $N^\downarrow = \{(x, y), (x', y')\}$ 表示织针 $N$ 在地面上的投影。对于 Ana(她是一位艺术家)来说,一条“地面闭合链”同样是 $k$ 根不同织针的序列 $N_1, N_2, \dots, N_k$(其中 $k \ge 3$),满足: $N_i^\downarrow \neq N_j^\downarrow$,对于所有 $1 \le i < j \le k$(即织针的投影必须全部不同); $N_1^\downarrow = \{(x_1, y_1), (x_2, y_2)\}, N_2^\downarrow = \{(x_2, y_2), (x_3, y_3)\}, \dots, N_k^\downarrow = \{(x_k, y_k), (x_{k+1}, y_{k+1})\}$,且 $(x_{k+1}, y_{k+1}) = (x_1, y_1)$。

考虑图中描绘的雕塑,它有以下四根织针: $A = \{(12, 12, 8), (10, 5, 11)\}, B = \{(12, 12, 8), (4, 14, 21)\}, C = \{(12, 12, 8), (12, 20, 8)\}, D = \{(4, 14, 21), (10, 5, 21)\}$。

该结构虽然没有真闭合链,但由于织针序列 $A, B, D$ 的存在,它不是一个没有地面闭合链的结构。

任务

编写一个程序,给定雕塑的织针,确定雕塑中是否存在真闭合链或地面闭合链。

输入格式

输入的第一行包含一个整数 $K$,表示雕塑中织针的数量。接下来的 $K$ 行,每行包含六个整数 $x_1, y_1, z_1, x_2, y_2, z_2$,表示织针的两个端点坐标 $\{(x_1, y_1, z_1), (x_2, y_2, z_2)\}$。任意两根不同的织针由不同的三元组集合表示。

输出格式

输出包含两行,每行一个字符串。第一行的字符串为:如果雕塑中存在真闭合链,则输出 True closed chains,否则输出 No true closed chains。第二行的字符串为:如果雕塑中存在地面闭合链,则输出 Floor closed chains,否则输出 No floor closed chains

数据范围

$1 \le K \le 50\,000$ $1 \le x_i, y_i, z_i < 1\,000$

样例

样例输入 1

4
12 12 8 10 5 11
12 12 8 4 14 21
12 12 8 12 20 8
4 14 21 10 5 21

样例输出 1

No true closed chains
Floor closed chains

样例输入 2

4
1 1 1 2 2 2
2 2 2 1 5 5
9 4 4 9 4 2
9 4 4 9 9 4

样例输出 2

No true closed chains
No floor closed chains

样例输入 3

3
50 50 50 100 100 100
100 100 100 50 50 90
50 50 90 50 50 50

样例输出 3

True closed chains
No floor closed chains

样例输入 4

3
1 1 5 1 3 7
1 3 7 4 4 5
4 4 5 1 1 5

样例输出 4

True closed chains
Floor closed chains

Figure 1. 雕塑的示意图,展示了织针 A, B, C, D 及其在地面上的投影。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.