#P18767. Gravity Zero Experiments

Gravity Zero Experiments

Gravity Zero Experiments

题目描述

科学家希望你帮助计算一项将在国际空间站上进行的重力实验的可能结果。

实验室中固定着 nn 根木条,每根木条都是三维空间中一条非空、长度非零的线段。保证任意两根木条不共面,也就是说,不存在同时包含这两条线段的平面。

实验开始前没有重力;实验开始后会产生沿某个方向 g⃗\vec g 的重力。

对于木条的非空集合 B⊆{1,2,…,n}B\subseteq\{1,2,\ldots,n\},如果可以选择某根木条上的一个点,放置一颗可以视为没有体积的小球,然后通过一系列操作访问 BB 中的所有木条,并回到同一个起始点,则称集合 BB 在该重力方向下是可循环的。

允许额外访问不属于 BB 的木条,也允许多次访问同一根木条。

小球可以执行以下操作:

  • 在当前所在的木条上,移动到该木条的任意其他点。
  • 从当前木条上放下小球。小球沿重力方向 g⃗\vec g 下落,并停在它遇到的另一根木条上最近的点。只有在小球确实能够停在某根其他木条上时,才允许执行下落操作。

对每个非空集合 BB,判断是否存在某个重力方向,使 BB 可循环。不同集合可以选择不同的重力方向。

输入格式

第一行包含整数 tt,表示测试用例数量。接下来是各个测试用例。

每个测试用例的第一行包含整数 nn,表示木条数量。

接下来 nn 行,每行包含六个整数

xi1,yi1,zi1,xi2,yi2,zi2,x_{i1},y_{i1},z_{i1},x_{i2},y_{i2},z_{i2},

表示第 ii 根木条的两个端点 (xi1,yi1,zi1)(x_{i1},y_{i1},z_{i1}) 和 (xi2,yi2,zi2)(x_{i2},y_{i2},z_{i2})。

数据范围

  • 1≤t≤10001\le t\le1000;
  • 1≤n≤201\le n\le20;
  • 所有端点的每个坐标都在 [−106,106][-10^6,10^6] 内;
  • 每根木条的两个端点不同;
  • 任意两根木条都不共面。

令 max⁡n\max n 为同一个输入文件中所有测试用例的最大木条数。根据它的值,tt 还满足下表:

max⁡n\max n [1,6][1,6] [7,10][7,10] [11,15][11,15] [16,20][16,20]
tt 的上限 1000 50 5 1

输出格式

每个测试用例输出一个长度恰好为 2n−12^n-1 的二进制字符串 ss。

对于每个 1≤i≤2n−11\le i\le2^n-1,令 BiB_i 是 ii 的二进制表示中为1的那些位置对应的木条集合,即

i=∑b∈Bi2b−1.i=\sum_{b\in B_i}2^{b-1}.

当且仅当 BiB_i 对某个重力方向可循环时,输出字符串的第 ii 个字符为1,否则为0。

样例

输入:

3
1
-1 1 -1 -1 -1 1
2
0 0 0 1 1 1
0 0 1 1 0 0
3
0 0 0 2 3 3
1 3 0 3 0 3
3 1 0 0 1 3

输出:

1
110
1111111