AtCoder ABC #220 : G - Isosceles Trapezium

これは解法は難しくないけど面倒な問題。
https://atcoder.jp/contests/abc220/tasks/abc220_g

問題

2次元座標中にN個の点が与えられる。各点iには重みC[i]が設定されている。
ここから4点選んで面積が正の等脚台形を作るとき、4点の重みの総和の最大値を求めよ。

解法

等脚台形の上底を成す2点と、下底を成す2点の垂直二等分線は一致する。
そこで、点の対に対しそれぞれ垂直二等分線を求め、点の対を分類しよう。

以後、同じ垂直二等分線を持つ点の対のグループを考える。
その際、面積が正の条件を満たすため、中点が一致するような点対は、重みの和が最大のもののみ残そう。
あとはグループ内において、重みの和が最大及び第2位のものを組み合わせればよい。

int N;
int X[1010],Y[1010];
ll C[1010];
map<pair<ll,ll>,ll> V,H;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i]>>C[i];
	}
	vector<pair<pair<ll,ll>,pair<int,int>>> V;
	FOR(y,N) FOR(x,y) {
		ll dx=(X[y]-X[x]);
		ll dy=Y[y]-Y[x];
		
		ll g=__gcd(abs(dx),abs(dy));
		dx/=g;
		dy/=g;
		if(dx<0) dx=-dx, dy=-dy;
		if(dx==0&&dy<0) dy=-dy;
		ll c=dx*(X[y]+X[x])+dy*(Y[y]+Y[x]);
		
		ll k=(dx<<32)+dy;
		V.push_back({{k,c},{x,y}});
	}
	sort(ALL(V));
	ll ret=-1;
	pair<ll,ll> pre={-1LL<<63,-1LL<<63};
	map<pair<int,int>,ll> memo;
	FORR2(v,a,V) {
		//cout<<v.first<<" "<<v.second<<"  "<<a.first<<" "<<a.second<<endl;
		if(v!=pre) {
			ll ma=-1LL<<60;
			FORR2(a,b,memo) {
				//cout<<"#"<<a.first<<" "<<a.second<<" "<<b<<endl;
				ret=max(ret,ma+b);
				ma=max(ma,b);
			}
			memo.clear();
		}
		pre=v;
		x=X[a.first]+X[a.second];
		y=Y[a.first]+Y[a.second];
		memo[{x,y}]=max(memo[{x,y}],C[a.first]+C[a.second]);
	}
	ll ma=-1LL<<60;
	FORR2(a,b,memo) {
		ret=max(ret,ma+b);
		ma=max(ma,b);
	}
	cout<<ret<<endl;
	
}

まとめ

等脚台形、一発で漢字変換できなかった…。