C. Diamond Miner

https://codeforces.ml/contest/1496/problem/C

题目大意

给出n个矿工的位置(0,y)和金矿的位置(x,0)，求出每个矿工和一个金矿连线的最小总和

思路

最小值的情况应该是n条连线无交点；
下面通过反证法证明:

假设存在两条连线相交，交点为0
根据三角形边长的特点:c < a + b
则有|AO|+|DO|>|AD|,|CO|+|BO|>|BC|,即:|AD|+|BC|<|AO|+|DO|+|CO|+|BO|=|AB|+|CD|。

所以答案为排序后的序列，依次相连线段的长度(注意正负不影响结果，故都按正数处理)。

官方扒的图

Code

#include<bits/stdc++.h>
#define IO  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define req(i,a,b) for(int i=a;i>=b;i--)
using namespace std; 
 
const int inf=0x3f3f3f3f;
typedef long long ll; 
const int N = 1e5+7;
const ll mod = 1e9+7; 

 
double a[N],b[N];
int main(){ 
    //IO;
    int t=1;
    cin>>t;
    while(t--){  
    	int n;
    	cin>>n; 
    	int i=0,j=0;
    	rep(k,1,2*n){
    		double x,y; 
    		scanf("%lf%lf",&x,&y);
    		if(x==0)a[++i]=y*y;
    		if(y==0)b[++j]=x*x;
    	}
    	sort(a+1,a+1+n);
    	sort(b+1,b+1+n);
    	double ans=0;
    	rep(i,1,n){
    		ans+=sqrt(a[i]+b[i]);
    	}printf("%.20lf\n", ans);
    }
    return 0;
}

C. Diamond Miner

原文：https://www.cnblogs.com/KeepInCode/p/14515585.html