Lyft Level 5 Challenge 2018 Final Round Div2 E - Optimal Polygon Perimeter
各点間のマンハッタン距離の和 = 長方形の周長ってのが完全に抜けてた
なんで解けなかったんだマジで
そういう問題最近SRMでやったし
問題
n頂点の凸多角形が与えられ、時計回りでi番目の頂点の座標は(x[i],y[i])である
このn個からk個の頂点v1, v2, ..., vkを選び、
Σ(viとvi+1間のマンハッタン距離)
を最大化したい
3 <= k <= nの全てのkについて↑の最大値を求めよ
3 <= n <= 3*10^5
|x|, |y| <= 10^8
解法
冒頭で言ったけどv1, v2, ..., vkについての
Σ(viとvi+1間のマンハッタン距離)
ってのは、これらk個の頂点を全て内側(or境界)に含むような長方形のうち最も小さいものの周長に等しい
○k>=4のとき
答えは明らかに
2{max(x)-min(x) + max(y)-min(y)}
となる
○k=3のとき
各点を↑で言った長方形の右上・右下・左下・左上それぞれにすると仮定したときの周長の最大値で答えを更新していけばいい
例えば点(a,b)を左下に固定するとき、長方形を右と上に出来る限り伸ばせば良いから
2{max(x)-a + max(y)-b}
で答えを更新みたいな感じ
他も同様にやればok
int n, x[300300], y[300300], mxx = -1<<30, mnx = 1<<30, mxy = -1<<30, mny = 1<<30, res3, res; signed main() { cin >> n; rep(i,n) { cin >> x[i] >> y[i]; chmax(mxx, x[i]), chmin(mnx, x[i]); chmax(mxy, y[i]), chmin(mny, y[i]); } res = (mxx-mnx + mxy-mny)*2; rep(i,n) { chmax(res3, (x[i]-mnx + y[i]-mny)*2); chmax(res3, (x[i]-mnx + mxy-y[i])*2); chmax(res3, (mxx-x[i] + y[i]-mny)*2); chmax(res3, (mxx-x[i] + mxy-y[i])*2); } cout << res3; rep(i,n-3) cout << ' ' << res; }