kmjp's blog

競技プログラミング参加記です

Codeforces #706 Div1 : A. Diamond Miner

ここら辺異様にやらかしてた時期だな。
https://codeforces.com/contest/1495/problem/A

問題

N個の点がY軸上、N個の点がX軸上にある。
それらを互いに任意の組み合わせでペアにし、N個の組を作ることを考える。
その時、各ペアの頂点間の距離の総和を最小化せよ。

解法

X座標及びY座標それぞれ、絶対値の小さい順に組み合わせるのが最適。

int T;
int N;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		vector<ll> X,Y;
		cin>>N;
		FOR(i,2*N) {
			cin>>x>>y;
			if(x==0) Y.push_back(abs(y));
			if(y==0) X.push_back(abs(x));
		}
		sort(ALL(X));
		sort(ALL(Y));
		reverse(ALL(Y));
		double ret=0;
		FOR(i,N) ret+=hypot(X[i],Y[N-1-i]);
		_P("%.12lf\n",ret);
		
	}
}

まとめ

Div1Aにしても簡単すぎる気がするけど、これは何だったんだろう。