[Deeplearning] 钻石矿工

首先画图

假设有两个点，那么去钻石的方案就如上图

那么我们就需要比较蓝线的长度与红线的长度

先看一下两点之间距离公式
\(\sqrt{(x-u)^2+(y-v)^2}\)

这个公式就是运用了勾股定理，一直两条边，求第三条

接着，我们比较蓝线与红线的长短

我们把它分为两个三角形（如图即可）

随后，根据三角形任意两条边之和大于第三条边,可以证明两条蓝线之和大于对应的红线，所以\(蓝线>红线\)，因此只需要让矿工取自己的\(i\)所对应的矿石即可

代码：

#include<bits/stdc++.h>
using namespace std;
const int Max=1e6+5;
long long a[Max],b[Max],q,p;
int x,y;
double ans;
int main()
{
	int t;
	cin>>t;
	while (t--)
	{
		int n;
		cin>>n;
		q=p=ans=0;
		for(int i=0;i<2*n;i++)
		{
			cin>>x>>y;
			if(x==0) a[q++]=abs(y);
			else b[p++]=abs(x);
		}
		sort(a,a+n);sort(b,b+n);
		for(int i=0;i<n;i++)
		{
			ans+=sqrt(double(a[i]*a[i]+b[i]*b[i]));
		}
		printf("%.15f\n",ans);
	}
	return 0;
}