P5936 [POI 1999 R2] 飞弹の题解

小清新计算几何。

以下皆口胡，有疏漏欢迎指正。

Updated：现已补充复杂度。

题意

平面上有

N

个红点和

N

个蓝点，要红蓝一一连线，要求不能出现交点（三点不共线），给出任意一种构造。

分析

考虑分治，如果找到一条分割线，使得两边的红蓝点数各自相同，然后可以分治下去，让两边分别各自匹配。

考虑怎么找这条线，有神秘

O(N^{D-1})

的算法，其中

D=2

是维数，可以自行搜索火腿三明治定理。

简单来说，就是：

给定两个物体，要求砍一刀使得同时平分两个物体。

证明就是：

对任何角度 $\alpha\in[0,\pi]$ ，均存在一条与 $X$ 轴成角度 $\alpha$ 的直线平分第一个物体。需使用介值定理）令 $\alpha$ 由 $0$ 增加到 $\pi$ ，再使用介值定理，则存在一条直线同时平分第二个物体。

对于这道题来说是离散版本的火腿三明治定理。

受到这个定理的启发，我们考虑如何寻找这条分割线。

考虑找到凸包上的一个点，可以直接寻找最左点（横坐标相同取最下），然后以极角排序，依次扫点，根据定理断言，一定能找到这样的一条线，分治下去即可。

复杂度

很明显期望是

O(N\log^2N)

的，但是最坏应该是

O(N^2\log^2N)

的。

真的吗，我们打个 dp 算一下。

CPP

#include <bits/stdc++.h>
using namespace std;

signed main()
{
    cin.tie(0)->sync_with_stdio(false), cout.setf(ios::fixed), cout.precision(4);

    // 平均
    vector<double> f(10001, 1e18);
    f[2] = 1;
    for (int n = 4; n <= 10000; ++n)
    {
        double sum = 0;
        for (int a = 2; a < n; a += 2)
        {
            sum += f[a] + f[n - a] + a;
        }
        sum /= n / 2 - 1;
        f[n] = sum + n * log2(n);
    }
    cout << "Average: " << f[10000] << '\n';

    // 最坏
    vector<double> g(10001, 1e18);
    g[2] = 1;
    for (int n = 4; n <= 10000; ++n)
    {
        double sum = 0;
        for (int a = 2; a < n; a += 2)
        {
            sum = max(sum, g[a] + g[n - a] + a);
        }
        g[n] = sum + n * log2(n);
    }
    cout << "Worst  : " << g[10000] << '\n';

    return 0;
}

可以发现最坏情况是

3\times10^8

，实测跑得飞快。

如果被卡了可以发扬人类智慧，随机旋转一个角度，但其实根本卡不满。

实现

Code

CPP

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define int ll

const int N = 1e6 + 10;
const int INF = 1e18;
const int MOD = 998244353;
using it2 = array<int, 2>;

pair<it2, int> a[N];
int n, ans[N], idx;

void solve(int l, int r)
{
    if (l > r)
    {
        return;
    }
    sort(a + l, a + r + 1), idx = l;
    sort(a + l + 1, a + r + 1, [&](auto u, auto v)
         { return (u.first[0] - a[idx].first[0]) * (v.first[1] - a[idx].first[1]) - (v.first[0] - a[idx].first[0]) * (u.first[1] - a[idx].first[1]) > 0; });
    int cnt = 0;
    for (int i = l + 1; i <= r; ++i)
    {
        if ((a[i].second > n) == (a[l].second > n))
        {
            --cnt;
        }
        else
        {
            ++cnt;
        }
        if (cnt == 1)
        {
            ans[a[l].second] = a[i].second, ans[a[i].second] = a[l].second;
            return solve(l + 1, i - 1), solve(i + 1, r);
        }
    }
}

signed main()
{
    cin.tie(0)->sync_with_stdio(0);
    cout.setf(ios::fixed);
    cout.precision(10);
    cin >> n;
    for (int i = 1; i <= n + n; ++i)
    {
        cin >> a[i].first[0] >> a[i].first[1], a[i].second = i;
    }
    solve(1, n + n);
    for (int i = 1; i <= n; ++i)
    {
        cout << ans[i] - n << '\n';
    }
    return 0;
}

P5936 [POI 1999 R2] 飞弹の题解

文章操作

P5936 [POI 1999 R2] 飞弹の题解

题意

分析

复杂度

实现

相关推荐

评论

P5936 [POI 1999 R2] 飞弹の题解