#A. 架桥问题

    Type: Default 1000ms 256MiB

架桥问题

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

架桥问题

题目背景

题目描述

一个岛国有nn座岛屿,它们在海面上恰好都分布在一个个整数坐标的点上。现在该国的国王请你为这个国家设计桥梁,使得这些桥梁可以连接所有的岛屿。但是,这个国家的国王有个强迫症,他希望所有桥梁都是南北或者东西走向的(即当且仅当两个岛的xx坐标相同或者yy坐标相同时,这两个岛之间可以建桥)。同时,他又非常吝啬,希望建造的桥梁的总长度最小,这里每段桥梁的长度为两个岛屿之间的直线距离。当然,这些桥允许交叉。

现在这个棘手的任务交给了你,你必须满足国王的所有要求,不然这个脾气怪异的国王可不知道会怎么处置没完成任务的你哦。

输入格式

输入第一行是一个正整数nn,代表平面上的点数。

接下来nn行,每行两个正整数x,yx,y,代表每一个点的坐标。

数据保证所有点不重复。

输出格式

一个正整数代表最小桥梁总长度。如果不能按要求建造桥梁,输出-1。

样例 #1

样例输入 #1

5
1 1
1 2
1 3
2 1
2 3

样例输出 #1

4

提示

数据范围

20%20\%的数据,1n104,1x,y3×1021\le n\le 10^4,1\le x,y\le 3×10^2

100%100\%的数据,1n5×105,1x,y5×1031\le n\le 5×10^5,1\le x,y\le 5×10^3

国庆集训S组模拟赛1

Not Attended
Status
Done
Rule
OI
Problem
4
Start at
2023-10-5 9:00
End at
2023-10-5 17:00
Duration
4 hour(s)
Host
Partic.
51