給你平面上的一些點,你必須用線段把它們全部連起來,但任何一條線段都必須是垂直或水平的,且線段的兩端點都必須在給定的點上。
問你要將所有的點連在一起,這些線段的總長度最小為多少。
輸入的第一行有一個整數T代表接下來有幾組測資,測資間以空白行分隔。
每組測資的第一行有一個整數 1≤N≤1000,
接下來有N行,每行各兩個整數(x,y)代表這個點的座標, 其中0≤x,y≤1000。
對每一組測資,輸出該測資的最小線段總和。
原TIOJ1326 / TFcis10 留社考。Problem Setter:seanwu
No. | Testdata Range | Score |
---|---|---|
1 | 0 | 100 |