Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define f first
- #define s second
- #define sqr(a) ((a)*(a))
- using namespace std;
- #pragma pack(1)
- int i, j, k, o, x, y, n, m, pr[5000+10], sz[5000+10];
- long double ans;
- struct my
- {
- int x;
- int y;
- int d;
- };
- my b[1000000*15];
- pair<int, int> a[5000+10];
- inline int dist(int x, int y, int xx, int yy)
- {
- int k=(sqr(x-xx)+sqr(y-yy));
- return k;
- }
- bool cmp(my a, my b)
- {
- if (a.d<b.d) return true;
- return false;
- }
- int get(int v)
- {
- if (v==pr[v]) return v;
- int res = get(pr[v]);
- pr[v] = res;
- return res;
- }
- int main()
- {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- cin>>n;
- for (i=1;i<=n;i++)
- {
- cin>>a[i].f>>a[i].s;
- pr[i]=i;
- sz[i]=0;
- }
- for (i=1;i<n;i++)
- {
- for (j=i+1;j<=n;j++)
- {
- int len=dist(a[i].f, a[i].s, a[j].f, a[j].s);
- m++;
- b[m].x=i;
- b[m].y=j;
- b[m].d=len;
- }
- }
- sort(b+1, b+m+1, cmp);
- for (i=1;i<=m;i++)
- {
- x=get(b[i].x);
- y=get(b[i].y);
- if (x!=y)
- {
- ans+=sqrt(sqr(a[b[i].x].f-a[b[i].y].f)+sqr(a[b[i].x].s-a[b[i].y].s));
- if (rand()&1) swap (x, y);
- pr[x]=y;
- }
- }
- cout.precision(12);
- cout<<fixed;
- cout<<ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement