algorithm/Kruskal given Points.cc at master · shahidul2k9/algorithm · GitHub

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <string.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>


using namespace std;

#define FOR( i, L, U ) for(int i=(int)L ; i<=(int)U ; i++ )
#define FORD( i, U, L ) for(int i=(int)U ; i>=(int)L ; i-- )
#define SQR(x) ((x)*(x))

#define INF INT_MAX


#define READ(filename)  freopen(filename, "r", stdin);
#define WRITE(filename)  freopen(filename, "w", stdout);

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<double> vd;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<vector<int> > vvi;
typedef vector<vector<int> > vvc;
typedef map<int, int> mii;
typedef map<string, int> msi;
typedef map<int, string> mis;
typedef map<string, string> mss;
typedef map<string, char> msc;

#define WHITE 0
#define GRAY 1
#define BLACK 2


#define EPS 1e-9
#define MAX_NODES 760
#define MAX_EDGES 1000000
struct Point{
    int x;
    int y;
};
struct Edge{
    int st;
    int en;
    double w;
};
Point node[MAX_NODES];
int pre[MAX_NODES];
Edge e[MAX_EDGES];
int nodes,edges;

double dist2d(Point a, Point b){

    return sqrt(SQR(a.x-b.x) + SQR(a.y-b.y));
}
bool comp(Edge e1, Edge e2){
    return e1.w - e2.w < EPS;
}

void resetPre(int n){
    for(int i=0;i<n;i++)pre[i]=i;
}
int findPre(int u){
    if(pre[u]==u)return u;
    else return pre[u]=findPre(pre[u]);
}
int main()
{
    READ("input.txt");
    //WRITE("output.txt");
    int i,j;
    while(scanf("%d", &nodes)==1){
        for(i=0;i<nodes;i++){
            scanf("%d %d", &node[i].x, &node[i].y);
        }
        edges = 0;
        for(i=0;i<nodes;i++)
            for(j=i+1;j<nodes;j++){
                e[edges].st = i;
                e[edges].en = j;
                e[edges].w = dist2d(node[i],node[j]);
                edges++;

            }
        resetPre(nodes);

        double mstw = 0;
        sort(e,e+edges,comp);

        for(i=0;i<edges;i++){
            int stp = findPre(e[i].st);
            int enp = findPre(e[i].en);
            if(stp!=enp){
                mstw +=e[i].w;
                pre[stp] = enp;

            }
        }
        printf("%.2lf\n", mstw);
    }

	return 0;
}