DMOPC '18 Contest 2 P1 - Pumpkin Patches

View as PDF

Submit solution

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

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…


2 \le P \le 100\,000
-1\,000\,000 \le x_i, y_i \le 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 coordinates of the i^\text{th} pumpkin.

Output Specification

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

Sample Input

0 0
1 0
0 2
1 1
0 1

Sample Output


Explanation for Sample

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


There are no comments at the moment.