Codeforces ECR #150 : F. Monocarp and a Strategic Game

コードはあんまり長くないんだけども。
https://codeforces.com/contest/1841/problem/F

問題

N個のグループがある。
各グループは4つの種族の生物がそれぞれ何匹かで構成される。
その数をA[i],B[i],C[i],D[i]とする。

この時、1番目と2番目、3番目と4番目は敵対関係にある。

N個のグループのうちいくつかを選んだ時、以下の総和の最大値はいくつか。

• 生物の総数
• 同種の生物のペアの総数
• 敵対関係にある生物のペアの総数を引いたもの

解法

各種の生物の総和をそれぞれa,b,c,dとすると、総和の値は(a-b)^2+(c-d)^2となる。
よって、N個の2次元ベクトル(A[i]-B[i],C[i]-D[i])を考え、そのうちいくつかを選んで和を取ったときに原点からの距離が最大化できればよい。
これはNベクトルが成す図形の凸法を考え、各頂点の距離を求めればよい。

int N;
int A[303030],B[303030],C[303030],D[303030];
pair<double,pair<ll,ll>> P[606060];

ostream& operator<<(ostream& os, __int128 v) {
	if(v==0) {
		return (os<<'0');
	}
	if(v<0) {
		os<<'-';
		v=-v;
	}
	
	string T;
	while(v) {
		T+=(char)('0'+(v%10));
		v/=10;
	}
	reverse(ALL(T));
	return (os<<T);
}

bool cmp(pair<ll,ll> a,pair<ll,ll> b) {
	return a.first*b.second-a.second*b.first<0;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d",&N);
	__int128 SX=0,SY=0;
	FOR(i,N) {
		scanf("%d%d%d%d",&A[i],&B[i],&C[i],&D[i]);
		P[i*2].second={A[i]-B[i],C[i]-D[i]};
		if(P[i*2].second.first==0&&P[i*2].second.second==0) {
			i--;
			N--;
			continue;
		}
		P[i*2+1].second={-A[i]+B[i],-C[i]+D[i]};
		P[i*2].first=atan2(P[i*2].second.second,P[i*2].second.first);
		P[i*2+1].first=atan2(P[i*2+1].second.second,P[i*2+1].second.first);
		if(P[i*2+1].first<P[i*2].first) {
			SX+=P[i*2].second.first;
			SY+=P[i*2].second.second;
		}
	}
	
	__int128 ma=SX*SX+SY*SY;
	sort(P,P+2*N);
	FOR(i,2*N) {
		SX+=P[i].second.first;
		SY+=P[i].second.second;
		ma=max(ma,SX*SX+SY*SY);
	}
	
	cout<<ma<<endl;
	
}

まとめ

最初の式変形を丁寧にやってれば、だいぶ道筋見えそう。