题解 CF1495A

Silence_water · 2021-03-12 16:51:58 · 题解

题目传送门

Analyse

由于将 x 或 y 取绝对值后答案不变，因此读入时直接转为绝对值即可。

考虑下图情况。

此时可能的答案有 ans_1=|AC|+|BD| 或 ans_2=|AD|+|BC|。

此时有 ans_2=|AD|+|BC|=|OC|+|OA|+|OD|+|OB|>|AC|+|BD|=ans_1。

故选择图中红线是最优的。

将 y=0 的点按照 |x| 从小到大排序，将 x=0 的点按照 |y| 从小到大排序，对应一一连线，这些连线的长度和就是答案了。

Solution

注意精度问题和强制转 long long。

#include<bits/stdc++.h>
using namespace std;
const int M=1e5+5;
int T,n,k,a[M],b[M];
int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        int a0=0,b0=0;
        for(int i=1;i<=2*n;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(y==0)a[++a0]=abs(x);
            else b[++b0]=abs(y);
        }
        sort(a+1,a+n+1);
        sort(b+1,b+n+1);
        double ans=0.0;
        for(int i=1;i<=n;i++)
            ans+=sqrt((long long)a[i]*a[i]+(long long)b[i]*b[i]);
        printf("%.11lf\n",ans);
    }
    return 0;
}

The end

感谢您的观看！如有不足，请麻烦指正哦。