QOJ.ac

QOJ

実行時間制限: 2 s メモリ制限: 128 MB 満点: 100

#5679. 链式三角形

統計

如果三角形 $\triangle ABC$ 满足以下条件,则称其被三角形 $\triangle DEF$ 链接:

  1. $\triangle DEF$ 的恰好一条边穿过 $\triangle ABC$ 的内部(在 $\triangle ABC$ 所在的平面内,见下图) 或者
  2. $\triangle DEF$ 的一个顶点位于 $\triangle ABC$ 的内部(在 $\triangle ABC$ 所在的平面内),且该顶点相邻的两条边位于 $\triangle ABC$ 平面的两侧

事实证明,$\triangle ABC$ 被 $\triangle DEF$ 链接当且仅当 $\triangle DEF$ 被 $\triangle ABC$ 链接。在这种情况下,我们称 $\triangle ABC$ 和 $\triangle DEF$ 是链接的。

三维空间中的一组点处于一般位置,是指没有四个点共面(这意味着没有三个点共线)。

已知在三维空间中,任意六个处于一般位置的点,至少有一种方法可以将这六个点分成两组,每组三个点,使得由这两个子集确定的三角形是链接的。注意,如果点处于一般位置,上述情况 2 不会发生,因为这会导致四个点位于 $\triangle ABC$ 的平面内。

编写一个程序,输入三维空间中的六个点,输出将这些点分成两组(每组三个点)并构成链接三角形的方法数量,以及各组中的点。

输入格式

输入包含六行,每行包含三个以空格分隔的双精度浮点数 $x, y, z$,表示一个点的坐标($-10 \le x, y, z \le 10$)。

输出格式

第一行输出一个十进制整数 $N$,表示找到的链接三角形对的数量。

接下来 $N$ 行,每行包含两个十进制整数 $m$ 和 $n$,表示选择点 $1, m, n$ 作为其中一个三角形,剩余的点作为另一个三角形,可以构成一对链接三角形。在每一行中,需满足 $m < n$,且这些行应按字典序排列。即如果 $m_1\ n_1$ 在 $m_2\ n_2$ 之上,则需满足 $m_1 < m_2$ 或者 ($m_1 = m_2$ 且 $n_1 < n_2$)。

样例

样例输入 1

1 0 0
-1 0 0
0 1 0.2
0 -1 0.2
0.2 0.2 1
0.2 0.2 -1

样例输出 1

3
2 3
2 5
3 4

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.