AT_arc063_d [ARC063F] すぬけ君の塗り絵 2

[problemUrl]: https://atcoder.jp/contests/arc063/tasks/arc063_d $ xy $ 平面上に、左下の頂点の座標が $ (0,\ 0) $、右上の頂点の座標が $ (W,\ H) $ で、各辺が $ x $ 軸か $ y $ 軸に平行な長方形があります。最初、長方形の内部は白く塗られています。 すぬけ君はこの長方形の中に $ N $ 個の点を打ちました。$ i $ 個目 ($ 1\ ≦\ i\ ≦\ N $) の点の座標は $ (x_i,\ y_i) $ でした。 すぬけ君は各 $ 1\ ≦\ i\ ≦\ N $ に対し、長方形の - $ x\ をみたす領域 $ - $ x\ >\ x_i $ をみたす領域 - $ y\ をみたす領域 $ - $ y\ >\ y_i $ をみたす領域 の $ 4 $ つの中から $ 1 $ つを選び、その領域を黒く塗ります。 塗りつぶしが終わったあとに残る白い長方形の周長を最大化するように塗る領域を選ぶとき、その最大の周長を求めてください。

N/A

N/A

### 制約 - $ 1\ ≦\ W,\ H\ ≦\ 10^8 $ - $ 1\ ≦\ N\ ≦\ 3\ \times\ 10^5 $ - $ 0\ ≦\ x_i\ ≦\ W $ ($ 1\ ≦\ i\ ≦\ N $) - $ 0\ ≦\ y_i\ ≦\ H $ ($ 1\ ≦\ i\ ≦\ N $) - $ W $, $ H $ (21:32 追記), $ x_i $, $ y_i $ は整数である - $ i\ ≠\ j $ ならば $ x_i\ ≠\ x_j $ かつ $ y_i\ ≠\ y_j $ である ### Sample Explanation 1 このケースでは、すぬけ君は以下の図のように長方形を塗りつぶすと残った白い長方形の周長が $ 32 $ となり、これが最大値である。 !\[842bb3939c9721d978d4e122b0bfff55.png\](https://atcoder.jp/img/arc063/842bb3939c9721d978d4e122b0bfff55.png)