TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P3074
  • Problem
  • P3074最小生成树7
    Limits : Time Limit : 10000 MS   Memory Limit : 65536 KB
    Judgment Tips : 1s
    Description

    平面上给你n个点,你要用平行于坐标轴的线段将他们连接成一棵树,并使线段的总长度最小。

    Input Format

    第一行正整数n
    接下来n行每行两个正整数x,y,表示坐标

    Output Format

    一个树,表示线段总长度的最小值

    Sample Input 1

    3
    1 1
    2 2
    1 3

    Sample Output 1

    3

    Sample Input 2

    6
    2 1
    2 3
    2 4
    2 5
    4 5
    5 2

    Sample Output 2

    9

    Hint

    样例解释:

           [2,2]
             |
    [1,1]----+----[1,3]
    

    数据范围:
    n<=2000
    1<=x<=500
    1<=y<=8
    保证坐标不重复