CF666D Chain Reaction 题解

CF666D Chain Reaction

题意

• 平面直角坐标系中有四个整点。
• 你可以将每个点水平或者垂直移动到一个整点，使得这四个点恰好成为一个平行于坐标轴的正方形的顶点（正方形不能退化成一个点）。
• 如果存在移动方案，则还要最小化对应点移动的最大距离。

题解

四个点明示超级大暴力，知道暴力怎么写就行了。

枚举 $2^4 = 16$ 种移动方向。

对于每种移动方向，由于可能有重合的，不妨设水平移动不少于垂直移动。

考虑每种有解的情况：

1. 2 水平 2 垂直：判断四个交点是否构成正方形。
2. 2 水平 1 垂直：相当于固定了正方形的一条边，枚举可能的正方形（只有两个）。
3. 2 水平 0 垂直：相当于固定了正方形的边长，相当于线性规划，也可以二分。

疯狂分类讨论 + 大力枚举就没了。

代码参考了兔兔的。

代码

const int inf = 1e9;
int p[4], x[4], y[4], ax[4], ay[4], bx[4], by[4], cx, cy, ans;
int lx[4], xy[4][5], ly[4], yx[4][5];

inline void check() {
	int d01 = abs(bx[0] == bx[1] ? by[0] - by[1] : bx[0] - bx[1]);
	int d02 = abs(bx[0] == bx[2] ? by[0] - by[2] : bx[0] - bx[2]);
	int d31 = abs(bx[3] == bx[1] ? by[3] - by[1] : bx[3] - bx[1]);
	int d32 = abs(bx[3] == bx[2] ? by[3] - by[2] : bx[3] - bx[2]);
	if (d01 != d02 || d02 != d31 || d31 != d32) return;
	do {
		int mx = 0;
		for (int i = 0; i < 4; i++) {
			if (x[i] != bx[p[i]] && y[i] != by[p[i]]) {
				mx = inf;
				break;
			}
			if (x[i] == bx[p[i]]) mx = max(mx, abs(y[i] - by[p[i]]));
			else mx = max(mx, abs(x[i] - bx[p[i]]));
		}
		if (mx < ans) {
			ans = mx;
			for (int i = 0; i < 4; i++) ax[i] = bx[p[i]], ay[i] = by[p[i]];
		}
	} while (next_permutation(p, p + 4));
}

inline void pd() {
	if (cx == 2 && cy == 2) {
		bx[0] = lx[0], by[0] = ly[0];
		bx[1] = lx[0], by[1] = ly[1];
		bx[2] = lx[1], by[2] = ly[0];
		bx[3] = lx[1], by[3] = ly[1];
		check();
	} else if (cy == 1) {
		bx[0] = lx[0], by[0] = ly[0];
		bx[1] = lx[1], by[1] = ly[0];
		bx[2] = lx[0], by[2] = ly[0] + (lx[0] - lx[1]);
		bx[3] = lx[1], by[3] = ly[0] + (lx[0] - lx[1]);
		check();
		bx[2] = lx[0], by[2] = ly[0] - (lx[0] - lx[1]);
		bx[3] = lx[1], by[3] = ly[0] - (lx[0] - lx[1]);
		check();
	} else if (cx == 1) {
		bx[0] = lx[0], by[0] = ly[0];
		bx[1] = lx[0], by[1] = ly[1];
		bx[2] = lx[0] + (ly[0] - ly[1]), by[2] = ly[0];
		bx[3] = lx[0] + (ly[0] - ly[1]), by[3] = ly[1];
		check();
		bx[2] = lx[0] - (ly[0] - ly[1]), by[2] = ly[0];
		bx[3] = lx[0] - (ly[0] - ly[1]), by[3] = ly[1];
		check();
	} else if (cy == 0) {
		int d = abs(lx[0] - lx[1]);
		sort(xy[0] + 1, xy[0] + 3);
		sort(xy[1] + 1, xy[1] + 3);
		int a[4] = {xy[0][1], xy[0][2] - d, xy[1][1], xy[1][2] - d};
		sort(a, a + 4);
		int z = (a[0] + a[3]) >> 1;
		bx[0] = lx[0], by[0] = z;
		bx[1] = lx[0], by[1] = z + d;
		bx[2] = lx[1], by[2] = z;
		bx[3] = lx[1], by[3] = z + d;
		check();
	} else {
		int d = abs(ly[0] - ly[1]);
		sort(yx[0] + 1, yx[0] + 3);
		sort(yx[1] + 1, yx[1] + 3);
		int a[4] = {yx[0][1], yx[0][2] - d, yx[1][1], yx[1][2] - d};
		sort(a, a + 4);
		int z = (a[0] + a[3]) >> 1;
		bx[0] = z, by[0] = ly[0];
		bx[1] = z + d, by[1] = ly[0];
		bx[2] = z, by[2] = ly[1];
		bx[3] = z + d, by[3] = ly[1];
		check();
	}
}

inline void solve() {
	ans = inf;
	for (int i = 0; i < 4; i++) rd(x[i]), rd(y[i]);
	for (int k = 0; k < 16; k++) {
		cx = cy = 0;
		for (int i = 0; i < 4; i++)
			if (k >> i & 1) {
				int o = -1;
				for (int j = 0; j < cx; j++) if (lx[j] == x[i]) o = j;
				if (~o) xy[o][++*xy[o]] = y[i];
				else xy[cx][*xy[cx] = 1] = y[i], lx[cx++] = x[i];
			} else {
				int o = -1;
				for (int j = 0; j < cy; j++) if (ly[j] == y[i]) o = j;
				if (~o) yx[o][++*yx[o]] = x[i];
				else yx[cy][*yx[cy] = 1] = x[i], ly[cy++] = y[i];
			}
		if (max(cx, cy) != 2 || (!cy && *xy[0] != 2) || (!cx && *yx[0] != 2)) continue;
		pd();
	}
	if (ans == inf) return print(-1), void();
	print(ans);
	for (int i = 0; i < 4; i++) print(ax[i], ' '), print(ay[i]);
}

int main() {
	for (int i = 0; i < 4; i++) p[i] = i;
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}