← 返回题目列表

AtCoder · arc063_d

F. Snuke 的着色 2

中文机器翻译题面 查看原题

分数: 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 可以通过如下绘制矩形得到:

842bb3939c9721d978d4e122b0bfff55.png

示例输入 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