TAP2016B - Finding the way

no tags 

[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]


The baking festival has arrived in town. This is a great opportunity for small businesses in the baking industry to collect some money and promote themselves. Each small business wanting to take part in the festival can do so by setting up a small stand in the hall where it takes place. For security reasons, each stand should be placed against one of the hall's walls. In its stall, each business can show its products and make the necessary arrangements to sell them to the public attending the festival. One important characteristic of the stands is that they offer a free sample of some products to whomever may want one. The goal is to show the great quality of the recipes and thus tempt passersby to buy at that stand.

The free samples bring a lot of people to the festival, wanting to eat the delicious desserts for no cost at all as they move around the hall. Most attendees buy some of the products to help the business who really deserve recognition. One of the festival's most famous visitors is Mr. Belly, who always goes by every single stand checking out the free samples, even going as far as giving a prize to the best of them all.

Mr. Belly doesn't want to waste too much time at the festival, so he would like to taste the free samples in all of the stands walking the least possible distance. In order to do this, he has the map printed on the festival's brochure, which was published in advance by the organizers. The map has a drawing of the shape of the hall, which in this case is a convex polygon. It also has markings for N important sites, two of which correspond to the entrance and exit of the hall, the other N-2 being the festival's stands. Each important site is represented by a point on the boundary of the polygon representing the hall's walls.

Mr. Belly is now asking for you to help him complete his mission. He will provide you with the coordinates in the Cartesian (X, Y) plane of the important sites in the hall, in counter-clockwise order (i.e. in the order in which he would visit them if he were to go through the hall keeping his right hand on its interior wall). He would like to know what's the minimum distance he must travel in order to visit all the stands, if he is to start at the entrance of the hall, finish at its exit and choose optimally the order in which he visits the stands.



There are multiple test cases in the input file. For each test case, the first line contains three integer numbers N, E and S. The integer N represents the number of important sites marked on the map, which are numbered from 1 to N (2 ≤ N  4000). The integers E and S represent the numbers of the sites corresponding to the hall's entrance and its exit, respectively ( E, S  N with E ≠ S). Each of the following N lines contains two integers and Y, representing the numbers on the i-th line the coordinates (X, Y) of the i-th important site (-104  X, Y  104). All the important sites are located in different points, and there always exists a convex polygon containing all of them in its boundary.



For each test case, print one line containing one rational number, representing the minimum distance Mr. Belly needs to walk in order to visit all of the festival's stands, starting at the entrance of the hall and finishing at its exit. Print the result with exactly 6 digits after the decimal marker, rounding if necessary.



6 1 6
1 0
2 0
3 1
2 2
1 2
0 1
6 1 4
0 0
10 0
20 0
20 1
10 1
0 1


Added by:Fidel Schaposnik
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:Argentinian Programming Tournament 2016