Official Editorial

https://scg3.piaoztsdy.cn/p/161

让我们先约定一些记号：

和代指要复原的两个平行平面。
和分别代指和上的点。
代指直线，即通过点和点的直线。
代表点在直线上。特别地，代表三点共线。
代表点不在直线上。特别地，代表三点不共线。
代表点在平面上。
代表直线在平面上。
代指和的法向量。
代指的法向量，其求法请参考 Luogu P4894。
代指所在的平面。
代表向量和共线。
代表向量和不共线。
代表对应元素平行，其中为直线，为平面。
代表对应元素垂直，其中为直线，为平面。
代指和所在的平面平行，这等价于。

在回到正题之前，让我们考虑三个特殊情况——

特殊情况：，此时输出 01 显然正确。

实际上，时一定有解——过点作平面，过点作平面，就可以得到满足要求的一组平面和，其中和是给出的两个点，代指直线。

特殊情况：，此时可以直接枚举划分方案。设所划分的组（每组个）点分别是（）和（），并用代指直线，代指直线。由立体几何基本事实 2（或者此处的公理 1）的推论——直线与平面相交有且只有一个公共点，可知。实际上，这个划分方案合法，当且仅当和平行或异面。

当和平行时，由立体几何基本事实推论 3，同时满足和的平面有且只有一个。过直线作平面，过直线作平面，就可以得到满足要求的一组平面和。

当和异面时，过点作直线，过点作直线，那么同时满足、、、、、、、的平面都是唯一确定的。根据线面平行的判定定理和面面平行的判定定理，由可知，由可知，从而 ——我们得到了满足要求的一组平面和。

当和相交时，设和的交点是，那么由和，可知 ——这与矛盾。也就是说，和相交时，不存在满足要求的平面和。

特殊情况：如果数据中存在点共线（即存在满足，其中），那么在所有合法的构造中，这个点一定落在同一个点。

让我们考虑使用反证法证明上述断言的正确性——让我们先假设上述断言是不正确的。

因为数据保证有解，所以一定存在另外一组平行但不重合的平面和，使得：

每个给定的点（包括）都恰好落在和中的某一个平面上。
和都包含了中的至少一个点。

因为直线与平面相交有且只有一个公共点，结合上面的性质，可知和都包含了中的恰好一个点。

根据上述论证，结合上述断言所需要的前提条件，我们得到了以下结论：

每个给定的点（包括）都恰好落在和中的某一个平面上。
和一共包含了中的个点。
。

这条结论显然矛盾，因此假设不成立，上述断言一定是正确的。

接下来，我们回到正题。在下面的叙述中，我们默认，因为的情况已经在上面讨论过了。

不难看出，任取个点（比如）就一定会有个点同时落在（或）上，因此我们只需要尝试次就能确定个落在同一个待复原平面上的点。

不妨设均在上，那么有：

由立体几何基本事实 2，如果，那么一定有。
对于满足的，。
对于，。

这启示我们（当时）利用 map 对每个不同方向的统计出现次数——一定有恰好个给定的点满足。

因此，我们只需要对每个出现次数符合要求的（可能的），判定剩下个满足的点是否在同一个法向量也为的平面上（如果判定成功，那么这个点所在的平面就是平面）就可以了——这可以通过（先任取中的个点——不妨设这个点分别是和，然后）对检查其是否满足和中的至少一条来实现。如果判定成功，我们直接对输出 0，对另外个点输出 1，即可完成构造。

然而，如果数据中存在点共线（即存在满足）的情况，那么我们在最坏情况下就需要判定次，上述做法的时间复杂度将退化为（其中是 map 贡献的，是化简法向量时使用的 __gcd 贡献的，且最坏情况下），无法通过此题。

让我们考虑对每个的判定进行优化。观察发现，我们可以另取个点（，），并（当时）利用（另一个）map 对每个不同方向的统计出现次数。对于每个：

若或（注意到这样的最多只有个，因为和各自只能对应一个方向的），依然按原来的方法判断。
若且，那么中一定包含了，我们只需要判定另外个是否满足即可。此时我们的另一个 map 就派上用场了——因为对于一定有（否则由得，然而和有公共点，矛盾），所以我们只需要判定（当时）是否有恰好个给定的点满足即可。

应用这一优化后，上述做法的时间复杂度将下降至，可以通过本题。

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 2e4 + 12;
struct P
{
	int x, y, z;
};
const P E = (P){0, 0, 0};
P operator-(P x, P y)
{
	return (P){x.x - y.x, x.y - y.y, x.z - y.z};
}
bool operator==(P x, P y)
{
	__int128 rt1 = 0, rt2 = 0;
	if (x.x == 0 && y.x != 0) return false;
	if (x.x != 0 && y.x == 0) return false;
	if (x.y == 0 && y.y != 0) return false;
	if (x.y != 0 && y.y == 0) return false;
	if (x.z == 0 && y.z != 0) return false;
	if (x.z != 0 && y.z == 0) return false;
	if (x.x != 0) rt1 = x.x, rt2 = y.x;
	if (x.y != 0) rt1 = x.y, rt2 = y.y;
	if (x.z != 0) rt1 = x.z, rt2 = y.z;
	if (x.x * rt2 != y.x * rt1) return false;
	if (x.y * rt2 != y.y * rt1) return false;
	if (x.z * rt2 != y.z * rt1) return false;
	return true;
}
bool operator!=(P x, P y)
{
	return !(x == y);
}
bool straight(P x, P y)
{
	return (__int128) x.x * y.x + (__int128) x.y * y.y + (__int128) x.z * y.z == 0;
}
P simplify(P a)
{
	int d = max(abs(a.x), max(abs(a.y), abs(a.z)));
	if (a.x) d = __gcd(abs(a.x), d);
	if (a.y) d = __gcd(abs(a.y), d);
	if (a.z) d = __gcd(abs(a.z), d);
	if (a.x < 0) d = -d;
	if (a.x == 0 && a.y < 0) d = -d;
	if (a.x == 0 && a.y == 0 && a.z < 0) d = -d;
	if (d) a.x /= d, a.y /= d, a.z /= d;
	return a;
}
P in[N];
bool ans[N];
P normal(int x, int y, int z)
{
	P a = in[x] - in[y], b = in[x] - in[z];
	int nx = a.y * b.z - a.z * b.y;
	int ny = a.z * b.x - a.x * b.z;
	int nz = a.x * b.y - a.y * b.x;
	return (P){nx, ny, nz};
}
bool operator<(P x, P y)
{
	if (x.x != y.x) return x.x < y.x;
	if (x.y != y.y) return x.y < y.y;
	return x.z < y.z;
}
bool check(int x, int y, int n)
{
	if (n == 2)
	{
		P p1 = in[x], p2 = in[y], p3 = in[6 - x - y], p4 = in[4];
		if (p1 - p2 == p1 - p3 || p1 - p2 == p1 - p4) return false;
		if (p1 - p2 == p3 - p4 || normal(x, y, 6 - x - y) != normal(x, y, 4))
		{
			ans[x] = ans[y] = true;
			for (int i = 1; i <= 2 * n; i++)
				printf("%d", ans[i]);
			puts("");
			return true;
		}
		return false;
	}
	memset(ans, 0, sizeof ans);
	ans[x] = ans[y] = true;
	map<P, int> mp1, mp2;
	int line = 2;
	P curline = in[x] - in[y];
	for (int i = 1; i <= 2 * n; i++)
	{
		if (i == x || i == y) continue;
		if (in[x] - in[i] == curline)
		{
			line++;
			ans[i] = true;
			continue;
		}
		P cur = simplify(normal(x, y, i));
		if (!mp1.count(cur)) mp1[cur] = 1;
		else mp1[cur]++;
	}
	if (line == n)
	{
		for (int i = 1; i <= 2 * n; i++)
			printf("%d", ans[i]);
		puts("");
		return true;
	}
	int xx = 1;
	while (x == xx || y == xx || ans[xx]) xx++;
	int yy = xx + 1;
	while (x == yy || y == yy || ans[yy]) yy++;
	int lines = 2;
	P curlines = in[xx] - in[yy];
	for (int i = 1; i <= 2 * n; i++)
	{
		if (i == x || i == y || i == xx || i == yy) continue;
		if (in[xx] - in[i] == curlines)
        {
            lines++;
            continue;
        }
		P cur = simplify(normal(xx, yy, i));
		if (!mp2.count(cur)) mp2[cur] = 1;
		else mp2[cur]++;
	}
	if (lines == n)
	{
		memset(ans, 0, sizeof ans);
		ans[xx] = ans[yy] = true;
		for (int i = 1; i <= 2 * n; i++)
		{
			if (i == xx || i == yy) continue;
			if (in[xx] - in[i] == curlines)
			{
				ans[i] = true;
				continue;
			}
		}
		for (int i = 1; i <= 2 * n; i++)
			printf("%d", ans[i]);
		puts("");
		return true;
	}
	for (map<P, int>:: iterator s = mp1.begin(); s != mp1.end(); s++)
	{
		if ((s -> second) != n - line) continue;
		P now = (s -> first);
		if (normal(x, y, xx) != now && normal(x, y, yy) != now)
		{
			if (!mp2.count(now)) continue;
			if (mp2[now] != n - lines) continue;
			for (int i = 1; i <= 2 * n; i++)
			{
				if (i == x || i == y || i == xx || i == yy) continue;
				if (ans[i]) continue;
				if (in[xx] - in[i] == curlines) continue;
				P cur = normal(x, y, i);
				if (cur == now) ans[i] = true;
			}
			for (int i = 1; i <= 2 * n; i++)
				printf("%d", ans[i]);
			puts("");
			return true;
		}
		else
		{
			int xxx = 1;
			while (x == xxx || y == xxx || normal(x, y, xxx) == now || ans[xxx]) xxx++;
			int yyy = xxx + 1;
			while (x == yyy || y == yyy || normal(x, y, yyy) == now || ans[yyy]) yyy++;
			bool oks = true;
			P nows = in[xxx] - in[yyy];
			if (!straight(nows, now)) oks = false;
			for (int i = 1; i <= 2 * n; i++)
			{
				if (i == x || i == y || i == xxx || i == yyy) continue;
				if (ans[i]) continue;
				if (in[xxx] - in[i] == nows) continue;
				if (normal(x, y, i) == now) continue;
				P cur = normal(xxx, yyy, i);
				if (cur != now) oks = false;
			}
			if (!oks) continue;
			for (int i = 1; i <= 2 * n; i++)
			{
				if (i == x || i == y || i == xxx || i == yyy) continue;
				if (ans[i]) continue;
				if (in[xxx] - in[i] == nows) continue;
				P cur = normal(x, y, i);
				if (cur == now) ans[i] = true;
			}
			for (int i = 1; i <= 2 * n; i++)
				printf("%d", ans[i]);
			puts("");
			return true;
		}
	}
	return false;
}
int solve()
{
	memset(ans, 0, sizeof ans);
	signed n;
	scanf("%d", &n);
	for (int i = 1; i <= 2 * n; i++)
	{
		signed x, y, z;
		scanf("%d %d %d", &x, &y, &z);
		in[i] = (P){x, y, z};
	}
	if (n == 1)
	{
		puts("01");
		return 0;
	}
	if (check(1, 2, n)) return 0;
	if (check(1, 3, n)) return 0;
	if (check(2, 3, n)) return 0;
	// The two statements below will be never executed.
	puts("I hate computational geometry!!!");
	return 0;
}
signed main()
{
	freopen("surface.in", "r", stdin);
	freopen("surface.out", "w", stdout);
	signed T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

暂无评论