P9397 题解

Nuyoah_awa · 2023-06-11 14:38:09 · 题解

题目大意

给定 n 个点，使其两两相连，要求两两相连的线段不能相交，求 |x_l-x_r| 之和的最小值。

题目分析

我们先不考虑两两互不相交，仅考虑 |x_l - x_r| 之和最小，我们可以将这些点都压缩为平面思考，也就是只考虑 x，我们不难发现，如果两两相邻的点相连可以使线段在 x 轴上没有重合，也就是说 |x_l - x_r| 之和最小。

于是我们再来考虑线段不能相交这个条件，我们发现对于相邻的两对点 a,b,c,d，上述连接方式是 a \to b,c \to d 我们发现 b_x \le c_x 且 b_y \neq c_y，也就是说，这两条线段是完全错开的。于是我们的连接方法就出来了。

但是你会发现交上去只有 5 pts。我们再回到题目，发现我们竟然没有判断无解的情况。

其实，只有当 n 是奇数，所有数无法两两相连是才会无解。

code

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

struct node{
    int x, y, id;
}a[500005];
int n, ans;

bool cmp(node u, node v)
{
    if(u.x == v.x)
        return u.y < v.y;
    return u.x < v.x;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1;i <= n;i++)
    {
        scanf("%d %d", &a[i].x, &a[i].y);
        a[i].id = i;
    }
    if(n & 1)
    {
        printf("-1\n");
        return 0;
    }
    sort(a + 1, a + n + 1, cmp);
    for(int i = 1;i <= n;i += 2)
        ans += a[i + 1].x - a[i].x;
    printf("%d\n", ans);
    for(int i = 1;i <= n;i += 2)
        printf("%d %d\n", a[i].id, a[i+1].id);
    return 0;
}