传送门

闲话

这题有蓝？？？

题意

平面上有 $2n$ 个点，需要将这些点分成两个大小为 $n$ 的集合，使得属于不同集合的点对距离的最小值最大，求出这个最大值，且给出一种构造方案。

$n \le 500$。

解析

观察题面，发现关键信息“最小值最大”，于是考虑二分，每次判断这个最小值可否不小于 $X$。

属于不同集合的点对距离的最小值不小于 $X$，也就是属于不同集合的点对距离都不小于 $X$，也就是点对距离小于 $X$ 的属于同一个集合。

于是利用并查集，枚举点对，如果距离小于 $X$ 就 merge，最后得到一些集合。

我们知道对于每一个集合，它里面的点要么全选要么不选，所以等价于要选一些集合，它们的大小之和为 $n$。再套一个 01 背包即可。构造方案只需记录从哪里转移过来的即可。具体实现看代码。

时间复杂度 $O(n^2 \log V)$，其中 $V$ 是两点间距离最大值。

代码

:::success[代码]

ll dis(ll x, ll y, ll x_, ll y_) {return (x - x_) * (x - x_) + (y - y_) * (y - y_);}
int sz[N], cnt = 0, ind[N];
vector<int> id[N];
bool f[N];
int pr[N];
bool check(ll X) {
    for (int i = 1; i <= n; i++) pre[i] = i, siz[i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) if (dis(xx[i], yy[i], xx[j], yy[j]) < X) {
            join_(i, j);
        }
    } cnt = 0;
    for (int i = 1; i <= n; i++) if (pre[i] == i) sz[++cnt] = siz[i];
    memset(f, false, sizeof(f)); f[0] = true;
    for (int i = 1; i <= cnt; i++) {
        for (int j = n; j >= sz[i]; j--) {
            f[j] |= f[j - sz[i]];
        }
    } return f[n / 2];
}
int main() {
    n = read<int>() * 2;
    for (int i = 1; i <= n; i++) {
        xx[i] = read<ll>(); yy[i] = read<ll>();
    } ll L = 0, R = (ll)1e19, mid, ans = -1;
    while (L <= R) {
        mid = ((__int128)L + R) >> 1;
        if (check(mid)) ans = mid, L = mid + 1;
        else R = mid - 1;
    } printf("%.10lf\n", sqrt(ans));
    for (int i = 1; i <= n; i++) pre[i] = i, siz[i] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) if (dis(xx[i], yy[i], xx[j], yy[j]) < ans) {
            join_(i, j);
        }
    } cnt = 0;
    for (int i = 1; i <= n; i++) if (pre[i] == i) sz[++cnt] = siz[i], ind[i] = cnt;
    for (int i = 1; i <= n; i++) id[ind[find_(i)]].push_back(i);
    memset(f, false, sizeof(f)); f[0] = true;
    for (int i = 1; i <= cnt; i++) {
        for (int j = n; j >= sz[i]; j--) {
            if (!f[j] && f[j - sz[i]]) {
                f[j] = true; pr[j] = i;
            }
        }
    } int xxx = n / 2;
    while (xxx) {
        int i = pr[xxx];
        for (int j = 0; j < (int)id[i].size(); j++) writeln(id[i][j]);
        xxx -= sz[i];
    }
    return fl();
}

:::

提交记录

二分是橙，并查集是黄，01 背包是橙，思维也不难，代码一小会写完了，建议降黄（逃（（（