ДОРЕШИВАНИЕ 2014 ACM-ICPC Украина, 2ой Раунд Украина, Сентябрь 13


Emos have relocated to newly built houses and decided to build a fence around their settlement. Emos are strange people, and they will cry if at least one section of the fence is not parallel to coordinate axis. Therefore, you have a task – to build a fence of minimal length around Emo's settlement in a way that all houses are located inside the area limited by the fence. The fence should be a polygon without self-intersections and self-tangencies with sides parallel to coordinate axis. Houses are points having coordinates. Some houses are allowed to be located at the fence itself.


The first line contains integer n (2n100 000) – number of houses. The following n lines contain descriptions of houses – each line contains two integers xi, yi (-109xi, yi109). All houses are located at different points, at least two x-coordinates and y-coordinates are different.


You need to print one integer – the minimal possible length of the fence.

Time limit 1 second
Memory limit 64 MiB
Input example #1
1 0
0 1
1 1
0 0
Output example #1
Source 2014 ACM-ICPC Ukraine, 2nd Round Ukraine, September 13, Problem J