CodeForces – 1495A – Diamond Miner

题意

给定 $2n$ 个点,其中 $n$ 个在 $x$ 轴上,另外 $n$ 个在 $y$ 轴上。现在要求每一个 $x$ 轴上的点与一个 $y$ 轴上的点连线,每个点恰好被连线一次。求所有线段的欧几里得距离之和

分析

首先根据数据范围 $n\leq 10^5$,在考场可以判断出贪心或二分。

之后看到样例解释的配图,发现可以抽象出:对于两条线段的模型。

由上图可以看出,对于四个点,只有两种连线方法:不交叉或交叉。

不交叉的欧几里得距离和为:$|AB|+|CD|$,交叉的欧几里得距离为 $|AC|+|BD|$.

经过肉眼观测,我们可以用小学数学证明不交叉一定优于交叉

由于三角形任意两边之和大于第三边,所以 $|AB|<|AO|+|BO|$,$|CD|<|CO|+|DO|$.

于是 $|AB|+|CD|<|AO|+|BO|+|CO|+|DO|=|AC|+|BD|$.

将结论推广到 $n$ 条线段,发现所有线段都不交叉是最优的,否则将交叉的两个线段交换,可以使距离和更小。

考虑如何按照这个方法,对所有点进行两两配对。

容易想到,把所有处于负半轴上的点,对称到正半轴上。这样处理后距离和不变。

所以,把 $x$ 轴上的点和 $y$ 轴上的点分别按照横竖坐标升序排序,排名相同的点进行配对,一定不会交叉。

代码

考场代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 1e5 + 10;
int T;
double a[MAXN], b[MAXN];
signed main() {
    cin >> T;
    while(T--) {
        int n, cnt1 = 0, cnt2 = 0; cin >> n;
        for(int i = 1; i <= 2 * n; i++) {
            int x, y; scanf("%lld%lld", &x, &y);
            if(x == 0) {
                if(y < 0) y *= -1;
                a[++cnt1] = y;
            }
            if(y == 0) {
                if(x < 0) x *= -1;
                b[++cnt2] = x;
            }
        }
        sort(a + 1, a + n + 1); sort(b + 1, b + n + 1);
        double ans = 0;
        for(int i = 1; i <= n; i++) {
            ans += sqrt(a[i] * a[i] + b[i] * b[i]);
        }
        printf("%.11lf\n", ans);
    }
    return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();