DMOPC '18 Contest 2 P1 - Pumpkin Patches

View as PDF

Submit solution



Points: 3
Time limit: 2.0s
Memory limit: 64M
Author:

Problem type

Roger is getting ready for his final1 Halloween of high school!

To celebrate, he goes to the land of Cartesia with Robert to grow P pumpkins. The i^{\text{th}} pumpkin is at point (x_i, y_i).

Unfortunately, the Pumpkin King of Cartesia has demanded that he surround his field of pumpkins with an axis-aligned rectangular fence first. Given that Roger is very poor, can you determine the minimum length of fencing he needs to enclose all his pumpkins?

Note: A pumpkin is considered within the fence if it lies on the fence.

1Assuming he doesn't fail to graduate...

Constraints

2 \leq P \leq 100\,000
-1\,000\,000 \leq x_i, y_i \leq 1\,000\,000
The locations of all pumpkins are pairwise distinct.

It is guaranteed the area enclosed by the fence will be positive.

Input Specification

The first line of input will contain a single integer, P.
The next P lines will each contain two space-separated integers, x_i and y_i, the co-ordinates of the i^{\text{th}} pumpkin.

Output Specification

A single integer, the amount of fencing Roger and Robert will need.

Sample Input

5
0 0
1 0
0 2
1 1
0 1

Sample Output

6

Explanation for Sample

The 4 corners of the fence are (0, 0), (1, 0), (1, 2), and (0, 2).


Comments

There are no comments at the moment.