概述
题号 | 难度 | \(AC\)时间及记录 |
---|---|---|
\(\texttt{CF1495A}\) | \(\texttt{洛谷难度:暂无评定}\) | \(\texttt{On 2021/03/12}\) |
解析
这是一道简单题。
题意不难理解。
我们考虑贪心。
实际上只有两种情况:
- 双线交叉。
- 双线不交叉。
因为两边之和大于第三边,
所以所有的线段都不交叉一定是最优的。
我们只需要按照 \(abs\) 值排个序,
然后小的和小的对,大的和大的对即可。
至于距离,相信大家都知道:
/*
Author:Xsmyy
Problem:CF1496C
Date:2021/03/10
*/
#include<bits/stdc++.h>
#define BetterIO ios::sync_with_stdio(false)
using namespace std;
int A[500001],B[500001];
int main(void)
{
BetterIO;
#ifndef ONLINE_JUDGE
freopen("SampleIN.in","r",stdin);
#else
#endif
register int Case;
cin>>Case;
while(Case--)
{
register int N;
cin>>N;
register int i;
for(i=1;i<=N;i++)A[i]=0;
for(i=1;i<=N;i++)B[i]=0;
register int C,D;
C=D=0;
for(i=1;i<=(N<<1);i++)
{
register int X,Y;
cin>>X>>Y;
if(!X)A[++C]=abs(Y);
else B[++D]=abs(X);
}
sort(A+1,A+C+1);
sort(B+1,B+D+1);
register double Ans;
Ans=0;
for(i=1;i<=N;i++)Ans+=1.0*sqrt(1.0*A[i]*A[i]+1.0*B[i]*B[i]);
printf("%.15lf\n",Ans);
}
return 0;
}