题解 CF1495A【Diamond Miner】

概述

题号 难度 \(AC\)时间及记录
\(\texttt{CF1495A}\) \(\texttt{洛谷难度:暂无评定}\) \(\texttt{On 2021/03/12}\)

解析

这是一道简单题。
题意不难理解。
我们考虑贪心。
实际上只有两种情况:

  • 双线交叉。
  • 双线不交叉。

因为两边之和大于第三边,
所以所有的线段都不交叉一定是最优的。
我们只需要按照 \(abs\) 值排个序,
然后小的和小的对,大的和大的对即可。
至于距离,相信大家都知道:

\[Dist=\sqrt{((X1-X2)^2 + (Y1-Y2)^2} \]

/*
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;
}
上一篇:痞子衡嵌入式:导致串行NOR Flash在i.MXRT下无法正常下载/启动的常见因素之Write Protection


下一篇:利用全局变量$_SESSION和register_shutdown_function自定义会话处理