Visits: 253

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;
}