2015
09-17

# Tsp

MGG is a poor truckman. One day he is asked to deliver packages for customers. There are n customers, where each customer specifies a location to pick up his/her package, and a location to deliver the package. Customers are labeled from 1 to n. For customer i, we denote the pickup location as i+, and the delivery location as i-. To deliver package for customer i, Mo must visit i+ before visiting i-.

However, the truck Mo drives has only a rear door, so the truck works as a stack: the last picked up package must be delivered first. If there are two packages i and j in the truck, and i is picked up before j, then i cannot be delivered unless j is delivered.

Mo knows all the coordinates of pickup and delivery locations. However, due to the censorship of the Great Fire Wall, Mo cannot visit any location more than once. What’s worse, there are additional restrictions:

– Mo can’t go to location j+ from i+ if j > i;
– Mo can’t go to location j- from i- if j < i;
– If Mo has visited location i-, location j+ will be removed from the world and cannot be visited any more if j < i.

Now Mo can choose any location to start. He wants to choose a shortest path to deliver packages for all the n customers. Please find the shortest path for him.

There are multiple test cases.
For each test case, the first line is an integer n, 0 < n <= 100.
Then n lines follow. There are 4 integers in each line. The integers in the i-th line indicate the x and y coordinates of i+, and the x and y coordinates of i-, respectively.

The distance between two locations is the Euclidean distance between them.

Input is terminated by end-of-file.

There are multiple test cases.
For each test case, the first line is an integer n, 0 < n <= 100.
Then n lines follow. There are 4 integers in each line. The integers in the i-th line indicate the x and y coordinates of i+, and the x and y coordinates of i-, respectively.

The distance between two locations is the Euclidean distance between them.

Input is terminated by end-of-file.

3
1 3 5 2
2 4 2 3
6 0 2 2
5
5 0 6 0
2 0 5 0
7 0 1 0
6 0 9 0
4 0 6 0

1+ 1- 3+ 2+ 2- 3-
2+ 1+ 1- 2- 3+ 3- 5+ 4+ 4- 5-

（1）放置点的顺序是递减的。

（2）一个区间一定可以分成多个区间的最优解的组合

1. 不能只说番茄啊，不是还有小黄瓜么、嘿嘿，我觉得，每种事物，都必然有它存在的道理，除了超乎法律公正之外的，我们没有权利去指责什么、

2. 如果当时你和他一起了，那又会怎样？很感动，你的文字很平淡，却能让我们想到你是一个怎样的女孩，让人感到可惜的爱情。祝你幸福！

3. 他们没有评估过毛左和宪政哪个对社会的伤害更大。显然崇上暴力的极左在文革表现已证明了！不要以为可以驾驭这思潮，一旦出笼，必会如洪水涛天！对社会的危害难以估量！

4. 他们没有评估过毛左和宪政哪个对社会的伤害更大。显然崇上暴力的极左在文革表现已证明了！不要以为可以驾驭这思潮，一旦出笼，必会如洪水涛天！对社会的危害难以估量！

5. 他们没有评估过毛左和宪政哪个对社会的伤害更大。显然崇上暴力的极左在文革表现已证明了！不要以为可以驾驭这思潮，一旦出笼，必会如洪水涛天！对社会的危害难以估量！