AIOC Banner

Problem: No (One) Left

Want to try solving this problem? You can submit your code online if you log in or register.

No (One) Left

Input File: leftin.txt
Output File: leftout.txt
Time Limit: 1 second

It is the distant year of 2012, and the doomsayers were right. Natural disasters have squashed cities and cleaved continents, massive solar flares have destroyed the ozone layer, and chemical pollution has turned the animals feral. Coda City, once a thriving metropolis, is now a wasteland. Besides you, there is no one left.

With the sun's merciless ultraviolet rays beating down during the day, and foul creatures roaming the streets at night, you have taken refuge in the sewers underneath the city. Fortunately, the sewers are very modern and have heating, lighting, and power outlets for your laptop. Unfortunately, you have no food with you, and so you must leave the sewer to stock up on supplies. The only time it is safe to surface is at sunset, when the sun is at its least harmful and the feral hamsters are still afraid to emerge.

Coda City consists of streets running north-south and east-west, forming a grid. Every street intersection has a manhole. The intersections are given coordinates as follows:

\includegraphics[height=6.5cm,trim=55 60 0 60,clip=true]{noleft-grid}

Some street intersections contain abandoned shopping trolleys, cast aside by panicking civilians during the flash floods and volcanic eruptions. If you collect all the food from all the trolleys, it should last you long enough for help to arrive. Since being outside at all is a massive risk, you decide to visit all the shopping trolleys in one fell swoop.

Your plan is as follows: You will emerge from any manhole. You will then run along the streets, emptying trolleys as you go. While you are doing this you must be wary of the sun's glare. If you try to head west, its powerful rays will blind you and you will trip, break your ankle and be eaten alive by feral hamsters. Once you have been to all the trolleys, you will climb down any manhole.

The longer you stay outside, the more vulnerable you are, so you must find the shortest route possible. Your task is, given the locations of abandoned trolleys within the city, to determine the shortest distance that you must travel above ground in order to collect food from all the abandoned trolleys.


The first line of the input file will contain a single integer, T, representing the number of trolleys ( 1  <= T  <= 100000). Each of the following T lines will be of the form x_i y_i, giving the coordinates of the ith trolley ( 0  <= x_i, y_i  <= 10000).


Your output file should contain a single integer: the shortest distance you must travel above ground to collect all the food from all the trolleys. Remember, you cannot go west for fear of certain death.

Sample Input

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

Sample Output



The trolleys in the sample data are shown in the diagram below. The thick black line shows one possible shortest path which visits all trolleys, starting from the bottom-left trolley and ending at the bottom-right trolley. The length of this path is 16.

\includegraphics[height=8.5cm,trim=56 56 40 30,clip=true]{noleft-eg}

Although many other paths are possible, there are no shorter paths, therefore the answer is 16.


The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated:  3 June 2023,  2:46pm AEST