Codeforces ECR #099 : E. Four Points

本番全然通らなくて唸ってた。
https://codeforces.com/contest/1455/problem/E

問題

2次元座標上で4つの点が与えられる。
これらの点を動かして、4点が軸に平行な正方形を成すようにしたい。
各点の移動量のマンハッタン距離の総和の最小値を求めよ。

解法

正方形の上端下端右端左端のうち3つは、移動前の点のX座標やY座標と一致させて良い。
あとは、元の4点が正方形のどの位置に行くかと、どの3辺の位置をどの点に合わせるかをそれぞれ総当たりしていこう。

int T;
vector<int> X(4),Y(4);

ll S,D;
vector<ll> R;

void add(int dif,int order) {
	S+=abs(dif);
	if(order==0) {
		return;
	}
	if(order==-1) dif=-dif;
	if(dif<=0) {
		D++;
	}
	else {
		D--;
		R.push_back(dif);
	}
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		FOR(i,4) cin>>X[i]>>Y[i];
		
		ll ret=1LL<<60;
		FORR(cx,X) FORR(cy,Y) {
			vector<vector<pair<int,int>>> P={
				{{0,0},{1,0},{1,1},{0,1}},
				{{0,0},{-1,0},{-1,1},{0,1}},
				{{0,0},{1,0},{1,-1},{0,-1}},
				{{0,0},{-1,0},{-1,-1},{0,-1}},
			};
			FORR(p,P) {
				vector<int> V={0,1,2,3};
				do {
					R.clear();
					S=D=0;
					FOR(i,4) {
						add(X[V[i]]-cx,p[i].first);
						add(Y[V[i]]-cy,p[i].second);
					}
					
					sort(ALL(R));
					ll pre=0;
					FORR(m,R) {
						if(D>=0) break;
						S+=1LL*(m-pre)*D;
						ret=min(ret,S);
						D+=2;
						pre=m;
					}
					ret=min(ret,S);
					
				} while(next_permutation(ALL(V)));
			}
		}
		
		cout<<ret<<endl;
		
			
	}
}

まとめ

そういう総当たりは思いつかなかった…。