time limit per test: 0.25 sec. memory limit per test: 4096 KB
There are N points given by their coordinates on a plane. All coordinates (xi,yi) are integers in a range from -10000 up to 10000 inclusive . It is necessary to construct a broken line satisfying the following conditions: 1. The broken line should be closed. 2. End points of each segment (verteces) of the broken line can only be the given points, and all given points should be used. 3. Each two consecutive segments of the broken line should form a corner of 90 degrees in each vertex point. 4. The sides of the broken line should be parallel to coordinate axes. 5. The broken line should have no self-crossing and self-contact. 6. The broken line should have the minimal length. You have to either find the length L of the constructed broken line, or determine that it is impossible to construct such a broken line.
First line contains the number N (4 <= N <= 10000) - amount of points. Each of the following N lines contains coordinates of points separated by space xi and yi (1 <= i <= N). Points are given in random order.
First line should contain the length of the broken line L or 0 if there is no solution.
: Alex Y. Suslov, Herman "Smash" Narkaytis
: 5th Southern Subregional Contest. Saratov 2002
Codeforces (c) Copyright 2010-2019 Mike Mirzayanov