题解 CF666D 【Chain Reaction】
xht
2020-03-11 23:33:27
> [CF666D Chain Reaction](https://codeforces.com/contest/666/problem/D)
## 题意
- 平面直角坐标系中有四个整点。
- 你可以将每个点水平或者垂直移动到一个整点，使得这四个点恰好成为一个平行于坐标轴的正方形的顶点（正方形不能退化成一个点）。
- 如果存在移动方案，则还要最小化对应点移动的最大距离。
## 题解
四个点明示超级大暴力，知道暴力怎么写就行了。
枚举 $2^4 = 16$ 种移动方向。
对于每种移动方向，由于可能有重合的，不妨设水平移动不少于垂直移动。
考虑每种**有解**的情况：
1. 2 水平 2 垂直：判断四个交点是否构成正方形。
2. 2 水平 1 垂直：相当于固定了正方形的一条边，枚举可能的正方形（只有两个）。
3. 2 水平 0 垂直：相当于固定了正方形的边长，相当于线性规划，也可以二分。
疯狂分类讨论 + 大力枚举就没了。
代码参考了兔兔的。
## 代码
```cpp
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;
}
```