架桥问题
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.
架桥问题
题目背景
题目描述
一个岛国有座岛屿,它们在海面上恰好都分布在一个个整数坐标的点上。现在该国的国王请你为这个国家设计桥梁,使得这些桥梁可以连接所有的岛屿。但是,这个国家的国王有个强迫症,他希望所有桥梁都是南北或者东西走向的(即当且仅当两个岛的坐标相同或者坐标相同时,这两个岛之间可以建桥)。同时,他又非常吝啬,希望建造的桥梁的总长度最小,这里每段桥梁的长度为两个岛屿之间的直线距离。当然,这些桥允许交叉。
现在这个棘手的任务交给了你,你必须满足国王的所有要求,不然这个脾气怪异的国王可不知道会怎么处置没完成任务的你哦。
输入格式
输入第一行是一个正整数,代表平面上的点数。
接下来行,每行两个正整数,代表每一个点的坐标。
数据保证所有点不重复。
输出格式
一个正整数代表最小桥梁总长度。如果不能按要求建造桥梁,输出-1。
样例 #1
样例输入 #1
5
1 1
1 2
1 3
2 1
2 3
样例输出 #1
4
提示
数据范围
对的数据,
对的数据,。
国庆集训S组模拟赛1
- 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