Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<cmath>
- #include<vector>
- #include<algorithm>
- #include<cstdio>
- using namespace std;
- int x[5001],y[5001];
- const double INF=100000000;
- double dest(int x1,int y1,int x2,int y2)
- {
- return sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
- }
- bool used[5001];
- double d[5001];
- int main()
- {
- freopen("unionday.in","r",stdin);
- freopen("unionday.out","w",stdout);
- int n;
- cin>>n;
- for(int i=0;i<n;i++)
- {
- cin>>x[i]>>y[i];
- }
- for(int i=0;i<n;i++) d[i]=INF;
- d[0]=0;
- double ans=0;
- for(int i=0;i<n;i++)
- {
- double best=INF;
- int cur=0;
- for(int j=0;j<n;j++)
- {
- if(d[j]<best && !used[j])
- {
- cur=j;
- best=d[j];
- }
- }
- used[cur]=true;
- ans+=best;
- for(int j=0;j<n;j++)
- {
- d[j]=min(d[j],dest(x[cur],y[cur],x[j],y[j]));
- }
- }
- cout.precision(8);
- cout<<fixed<<ans<<endl;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement