1327 . 最小格子生成樹-EXTREME

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

92.1% (35/38)

Submission's AC Ratio

55.3% (73/132)

Tags

X-TFcis TFcis

Description

給你平面上的一些點，你必須用線段把它們全部連起來，但任何一條線段都必須是垂直或水平的，且線段的兩端點都必須在給定的點上。

問你要將所有的點連在一起，這些線段的總長度最小為多少。

Input Format

輸入的第一行有一個整數 T 代表接下來有幾組測資，測資間以空白行分隔。

每組測資的第一行有一個整數 1≤N≤105

接下來有 N 行，每行各兩個整數 (x,y) 代表這個點的座標, 其中 0≤x,y<231。

Output Format

對每一組測資，輸出該測資的最小線段總和。

Sample Input 1

2

7
0 0
0 3
1 0
1 2
2 1
2 2
2 3

2
3 4
3 10

Sample Output 1

8
6

Hints

Problem Source

原TIOJ1327 / TFcis10 留社考。Problem Setter：seanwu

Subtasks

No. Testdata Range Score
1 0 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
Submit
Back to Top