Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstring>
- #include <cmath>
- using namespace std;
- double dist(int x1,int y1,int x2,int y2)
- {
- return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
- }
- int main()
- {
- int n,i,j;
- int x[101],y[101];
- bool vis[101];
- double res=0.0,najmalo_dist;
- int cnt,teme;
- memset(vis,false,sizeof(vis));
- cin>>n;
- for(i=1;i<=n;i++)
- {
- cin>>x[i]>>y[i];
- }
- cnt=1;
- vis[1]=true;
- double t;
- while(cnt<n)
- {
- najmalo_dist=1000000.0; //very big double
- teme=-1;
- for(i=1;i<=n;i++) //za poseteni
- {
- if(vis[i]==false) continue;
- for(j=1;j<=n;j++) //za neposeteni
- {
- if(vis[j]==true) continue;
- t=dist(x[i],y[i],x[j],y[j]);
- if(t<najmalo_dist)
- {
- najmalo_dist=t;
- teme=j;
- }
- }
- }
- res+=najmalo_dist;
- vis[teme]=true;
- cnt++;
- }//end_while
- int r=res*100;
- cout<<r/100<<"."<<(r/10)%10<<r%10<<endl;
- return 0;
- }
Add Comment
Please, Sign In to add comment