题解 CF666D 【Chain Reaction】
Kewth
2020-02-04 22:11:36
枚举每个点是走横坐标还是走纵坐标，得到 4 条直线，
要求放置的每个点要占据一条直线，将直线去重，分类讨论：
---
1. **两条横线两条竖线**
放置的点一定是四个交点，判断一下是否是正方形然后统计。
统计的话直接 $O(4!)$ 枚举点之间的配对方式即可。
---
2. **两条横线一条竖线**（一条横线两条竖线同）
首先两个交点一定要放，那么确定了正方形边长为两条横线的距离。
枚举剩下两个点在左边还是右边，分别统计。
---
3. **两条横线**（两条竖线同）
四个点都要放在两条平行线上，显然一条直线放两个点，
那么可以确定正方形边长 $D$ ，两个横坐标是形如 $x$ 和 $x + D$ 这样的。
求出最优的 $x$ ，一个简单的方式是三分，
因为不难发现答案是关于 x 的单峰函数。
更优秀的方式是直接解式子。
设第一条直线原有的两个点横坐标为 $x_1$, $x_2$ ，另外一条为 $x_3$, $x_4$ 。
在每条直线上枚举配对方式，
不妨设 $x_1$, $x_2$, $x_3$, $x_4$ 分别与 $x$, $x + D$, $x$, $x + D$ 配对。
那么这部分的答案就是 $max(|x_1 - x|, |x_2 - x - D|, |x_3 - x|, |x_4 - x - D|)$
令 $x_5 = x_2 - D$, $x_6 = x_4 - D$ ，上式为
$max(|x_1 - x|, |x_5 - x|, |x_3 - x|, |x_6 - x|)$
这个式子也就是数轴上 $x$ 到四个位置的距离的最大值，
取这四个位置的最大最小值的平均数为 $x$ 即可令这个值最小。
---
至于其他情况不难证明都是不存在合法方案的。
---
参考实现：
```cpp
#include <cstdio>
#include <algorithm>
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long ll;
struct {
inline operator int () { int x; return scanf("%d", &x), x; }
inline operator ll () { ll x; return scanf("%lld", &x), x; }
inline operator char () { char x[3]; return scanf("%s", x), *x; }
} read;
int calc(int *x, int *y, int *nx, int *ny, int *ansp) {
int p[4] = {0, 1, 2, 3}, res = 1000000000;
do {
int now = 0;
for(int i = 0; i < 4; i ++)
if(x[i] == nx[p[i]])
now = std::max(now, std::abs(y[i] - ny[p[i]]));
else if(y[i] == ny[p[i]])
now = std::max(now, std::abs(x[i] - nx[p[i]]));
else
now = 1000000000;
if(now < res) {
res = now;
for(int i = 0; i < 4; i ++) ansp[i] = p[i];
}
} while(std::next_permutation(p, p + 4));
return res;
}
int main() {
const int _ = 20200202; // magic
int T = read;
while(T --) {
int x[5], y[5];
for(int i = 0; i < 4; i ++) {
x[i] = read;
y[i] = read;
}
x[4] = 1;
y[4] = 0;
int ans = 1000000000;
int ansx[4], ansy[4];
int nx[4], ny[4];
auto update = [&]() {
int p[4] = {0, 1, 2, 3};
int tmp = calc(x, y, nx, ny, p);
#if 0
debug(">>> get %d\n", tmp);
for(int i = 0; i < 4; i ++)
debug("%d %d\n", nx[p[i]], ny[p[i]]);
#endif
if(tmp < ans) {
ans = tmp;
if(x[4] == 1)
for(int i = 0; i < 4; i ++) {
ansx[i] = nx[p[i]];
ansy[i] = ny[p[i]];
}
if(x[4] == 0)
for(int i = 0; i < 4; i ++) {
ansx[i] = ny[p[i]];
ansy[i] = nx[p[i]];
}
}
};
for(int S = 0; S < 16; S ++) {
int xx[4] = {_, _, _, _}, yy[4] = {_, _, _, _};
for(int i = 0; i < 4; i ++) {
int *tar = (S >> i & 1) == x[4] ? xx : yy;
int v = (S >> i & 1) == x[4] ? x[i] : y[i];
int j = 0;
while(tar[j] != _ and tar[j] != v) ++ j;
tar[j] = v;
}
if(xx[2] != _ or yy[2] != _) continue;
if(xx[1] == _ and yy[1] == _) continue;
if(yy[0] == _) {
std::swap(xx, yy);
std::swap(x, y);
}
if(xx[0] == _) {
int d = std::abs(yy[0] - yy[1]);
ny[0] = ny[2] = yy[0];
ny[1] = ny[3] = yy[1];
for(int T = 0; T < 4; T ++) {
int shit[2] = {T >> 1, T & 1};
int l = 1000000000, r = - 1000000000;
for(int i = 0; i < 4; i ++) {
int o = y[i] == yy[1];
int v = shit[o] ? x[i] + d : x[i];
shit[o] ^= 1;
l = std::min(l, v);
r = std::max(r, v);
}
// debug("fcuk %d %d %d\n", d, l, r);
int mid = (l + r + 1) >> 1;
nx[0] = nx[1] = mid;
nx[2] = nx[3] = mid - d;
update();
}
continue;
}
if(yy[1] == _) {
std::swap(xx, yy);
std::swap(x, y);
}
if(xx[1] == _) {
int d = std::abs(yy[0] - yy[1]);
nx[0] = nx[1] = xx[0];
ny[0] = ny[2] = yy[0];
ny[1] = ny[3] = yy[1];
nx[2] = nx[3] = xx[0] - d;
update();
nx[2] = nx[3] = xx[0] + d;
update();
continue;
}
if(std::abs(xx[0] - xx[1]) == std::abs(yy[0] - yy[1])) {
nx[0] = nx[1] = xx[0];
nx[2] = nx[3] = xx[1];
ny[0] = ny[2] = yy[0];
ny[1] = ny[3] = yy[1];
update();
}
}
if(ans == 1000000000) puts("-1");
else {
printf("%d\n", ans);
for(int i = 0; i < 4; i ++)
printf("%d %d\n", ansx[i], ansy[i]);
}
}
}
```