Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define speed ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
- #define pb push_back
- #define mp make_pair
- #define F first
- #define S second
- #define sz(x) (int)(x.size())
- #define all(x) x.begin(), x.end()
- typedef long long ll;
- typedef unsigned long long ull;
- const ll INF = LLONG_MAX;
- const int inf = INT_MAX;
- const int N = 5005;
- const ll MOD = 1e9+7;
- const double EPS = 1e-9;
- short int p[N], r[N];
- void make_set(short int v){
- p[v] = v;
- r[v] = 1;
- }
- short int find_set(short int v){
- if(p[v] == v)
- return v;
- return p[v] = find_set(p[v]);
- }
- void union_sets(short int u, short int v){
- u = find_set(u);
- v = find_set(v);
- if(u == v)
- return;
- if(r[u] < r[v])
- swap(u, v);
- p[v] = u;
- if(r[u] == r[v])
- r[u]++;
- }
- struct edge{
- short int u, v;
- int w;
- };
- struct cor{
- short int x, y;
- };
- bool cmp(edge a, edge b){
- return a.w < b.w;
- }
- vector <edge> edges;
- vector <cor> c;
- void solve(){
- short int n, x, y;
- double ans = 0;
- cin >> n;
- for(short int i = 1; i <= n; i++)
- make_set(i);
- for(short int i = 1; i <= n; i++){
- cin >> x >> y;
- c.pb({x, y});
- }
- for(short int i = 0; i < n; i++)
- for(short int j = i+1; j < n; j++)
- edges.pb({i + 1, j + 1, (int)(c[i].x - c[j].x) * (int)(c[i].x - c[j].x) + (int)(c[i].y-c[j].y) * (int)(c[i].y-c[j].y)});
- sort(all(edges), cmp);
- for(auto x : edges){
- if(find_set(x.u) != find_set(x.v)){
- union_sets(x.u, x.v);
- ans += sqrt(x.w);
- }
- }
- cout << fixed << setprecision(6) << '\n';;
- cout << ans << '\n';
- }
- int main(){
- speed;
- freopen("unionday.in","r",stdin);
- freopen("unionday.out","w",stdout);
- int T = 1;
- while(T--)
- solve();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement