include iostream include cstdio include vector include cmath include a

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <set>
using namespace std;
const long long INF = 1000000000;
struct point
{
short x, y;
point(const short& _x, const short& _y) : x(_x), y(_y) {}
point operator - (const point& a)
{
return point(x - a.x, y - a.y);
}
double len()
{
return sqrt((double)(x * x + y * y));
}
};
vector <point> cords;
vector < pair < double, pair <unsigned short, unsigned short> > > g;
int main()
{
freopen("randommst.in", "r", stdin);
freopen("randommst.out", "w", stdout);
int n;
cin >> n;
cords.resize(n, point(0, 0));
for (int i = 0; i < n; ++i)
cin >> cords[i].x >> cords[i].y;
for (int i = n - 1; i >= 0; --i)
{
for (int j = i - 1; j >= 0; --j)
{
g.push_back(make_pair((cords[i] - cords[j]).len(), make_pair(j, i)));
}
cords.pop_back();
}
int m = g.size();
double cost = 0;
vector < pair <unsigned short, unsigned short> > res;
sort(g.rbegin(), g.rend());
vector <unsigned short> tree_id(n);
for (int i = 0; i < n; ++i)
tree_id[i] = i;
for (int i = m - 1; i >= 0; --i)
{
unsigned short a = g[i].second.first, b = g[i].second.second;
double l = g[i].first;
g.pop_back();
if (tree_id[a] != tree_id[b])
{
cost += l;
res.push_back(make_pair(a, b));
unsigned short old_id = tree_id[b], new_id = tree_id[a];
for (int j = 0; j < n; ++j)
if (tree_id[j] == old_id)
tree_id[j] = new_id;
}
}
cout << fixed << setprecision(12) << cost << endl;
for (int i = 0; i < res.size(); ++i)
cout << res[i].first + 1 << " " << res[i].second + 1 << endl;
return 0;
}