897 . Decision Trees
Description
Consider a two-dimensional space with a set of points (xi,
yi) that satisfy xi < xj
and yi > yj for all i < j.
We want to have them all connected by a directed tree whose edges go toward
either right (x positive) or upward (y positive). The
figure below shows an example tree.
Figure 1: An example tree
Write a program that finds a tree connecting all given points with the shortest total length of edges.
Input Format
There are multiple test cases, the first line contains an integer T<=50 indicating the total number of test cases. For each test case, the input begins with a line that contains an integer n (1 <=
n <= 1000), the number of points. Then n lines follow. The
i-th line contains two integers xi and yi
(0 <= xi, yi <= 10000), which give
the coordinates of the i-th point.
Output Format
For each test case please print the shortest total length of edges in a line.
Sample Input 1
2 5 1 5 2 4 3 3 4 2 5 1 1 10000 0
Sample Output 1
12 0
Hints
Problem Source
Migrated from old NTUJ.
M-judge 10107
Subtasks
| No. | Testdata Range | Score |
|---|