Problem:


Score : 1600 points

Problem Statement

There is a rectangle in the xy-plane, with its lower left corner at (0, 0) and its upper right corner at (W, H). Each of its sides is parallel to the x-axis or y-axis. Initially, the whole region within the rectangle is painted white.

Snuke plotted N points into the rectangle. The coordinate of the i-th (1 ≦ i ≦ N) point was (x_i, y_i).

Then, for each 1 ≦ i ≦ N, he will paint one of the following four regions black:

the region satisfying x < x_i within the rectangle

the region satisfying x > x_i within the rectangle

the region satisfying y < y_i within the rectangle

the region satisfying y > y_i within the rectangle

Find the longest possible perimeter of the white region of a rectangular shape within the rectangle after he finishes painting.

Constraints

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, added), x_i and y_i are integers.

If i ≠ j, then x_i ≠ x_j and y_i ≠ y_j.

Input

The input is given from Standard Input in the following format:

W H N
x_1 y_1
x_2 y_2
:
x_N y_N

Output

Print the longest possible perimeter of the white region of a rectangular shape within the rectangle after Snuke finishes painting.

Sample Input 1

10 10 4
1 6
4 1
6 9
9 4

Sample Output 1

32

In this case, the maximum perimeter of 32 can be obtained by painting the rectangle as follows:

Sample Input 2

5 4 5
0 0
1 1
2 2
4 3
5 4

Sample Output 2

12

Sample Input 3

100 100 8
19 33
8 10
52 18
94 2
81 36
88 95
67 83
20 71

Sample Output 3

270

Sample Input 4

100000000 100000000 1
3 4

Sample Output 4

399999994



Sample input:
10 10 4
1 6
4 1
6 9
9 4


Sample output:
32

Submission status: Wrong Answer

Solution code:
wid, hei, nn = [int(x) for x in input().split()]
N, E, W, S = hei, wid, 0, 0
N2, E2, W2, S2 = hei, wid, 0, 0

for _ in range(nn):
    x, y = [int(x) for x in input().split()]
    n, e, w, s = N - y, E - x, x - W, y - S
    m = min(n, e, w, s)

    if m == n:
        N = min(N, y)
    elif m == e:
        E = min(E, x)
    elif m == w:
        W = max(W, x)
    else:
        S = max(S, y)

    if hei - y < y:
        N2 = min(N2, y)
    else:
        S2 = max(S2, y)

    if wid - x < x:
        E2 = min(E2, x)
    else:
        W2 = max(W2, x)

print(max(
    (N - S) * 2 + (E - W) * 2,
    (N2 - S2) * 2 + wid * 2,
    hei * 2 + (E2 - W2) * 2
))

Submission status: Runtime Error

Solution code:
def main():
    N = input()
    edges = [raw_input() for _ in range(N-1)]
    K = input()
    VP = [raw_input() for _ in range(K)]

    VP = [map(int, _.strip().split()) for _ in VP]
    edges = [map(int, _.strip().split()) for _ in edges]
    # print VP
    # print edges
    scores = {}
    for n_idx, value in VP:
        scores[n_idx] = [value]
    pre_defined = scores.keys()
    # print scores
    def check(value, n1, n2):
        if value == (n1 - n2) or value == (n2 - n1):
            return True
        return False

    for idx in pre_defined:
        for n1, n2 in [l for l in edges if idx in l]:
            v = scores[idx][0]
            n = n1 if idx == n2 else n2
            scores[n] = [_ for _ in scores.get(n, []) if check(_, n1, n2)] + [v - 1, v+1]
    for n1, n2 in edges:
        # print n1, n2
        if scores.get(n1) is None and scores.get(n2) is None:
            pass
        else:
            if scores.get(n1) is None:
                for v in scores.get(n2, []):
                    scores[n1] = [_ for _ in scores.get(n1, []) if check(_, n1, n2)] + [v - 1, v+1]
            elif scores.get(n2) is None:
                for v in scores.get(n1, []):
                    scores[n2] = [_ for _ in scores.get(n2, []) if check(_, n1, n2)] + [v - 1, v+1]

        # print scores.get(n1), scores.get(n2) 
        # print "----------"

    # decide step
    adding = []
    for n in range(1, N+1):
        v = scores.get(n, [None])[0]
        adding.append(v)
    if all([_ is not None for _ in adding]):
        print "Yes"
        for a in adding:
            print a
    else:
        print "No"


    # print scores


if __name__ == '__main__':
    main()