分数: 1600 点
问题陈述
中有一个矩形 xy- 平面,其左下角位于 (0, 0) 及其右上角 (W, H)。它的每条边都平行于 x- 轴或 y- 轴。最初,矩形内的整个区域被漆成白色。
阴谋策划 N 指向矩形。的坐标 i-th (1 ≦ i ≦ N)点是 (x_i, y_i).
然后,对于每个 1 ≦ i ≦ N,他会将以下四个区域之一涂成黑色:
- 满足的区域 x < x_i 在矩形内
- 满足的区域 x > x_i 在矩形内
- 满足的区域 y < y_i 在矩形内
- 满足的区域 y > y_i 在矩形内
画完后,求矩形内矩形白色区域的最长可能周长。
约束
- 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 是整数。
- If i ≠ j,那么 x_i ≠ x_j 和 y_i ≠ y_j.
输入
输入由标准输入按以下格式给出:
W H N x_1 y_1 x_2 y_2 : x_N y_N
输出
Snuke 完成绘画后,在矩形内打印矩形白色区域的最长周长。
示例输入 1
10 10 4 1 6 4 1 6 9 9 4
示例输出 1
32
在这种情况下,最大周长 32 可以通过如下绘制矩形得到:
示例输入 2
5 4 5 0 0 1 1 2 2 4 3 5 4
示例输出 2
12
示例输入 3
100 100 8 19 33 8 10 52 18 94 2 81 36 88 95 67 83 20 71
示例输出 3
270
示例输入 4
100000000 100000000 1 3 4
示例输出 4
399999994