fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define FR0(i,N) for(i=0;i<(N);i++)
  4. #define FR1(i,N) for(i=1;i<=(N);i++)
  5. #define FRN(i,k,N) for(i=k;i<(N);i++)
  6. #define pf printf
  7. #define db double
  8. #define max3(a,b,c) max(max(a,b),c)
  9. #define min3(a,b,c) min(min(a,b),c)
  10. #define sci(n) scanf("%d",&n)
  11. #define scl(n) scanf("%lld",&n)
  12. #define scf(n) scanf("%f",&n)
  13. #define scd(n) scanf("%lf",&n)
  14. #define scs(s) scanf("%s",&s)
  15. #define scll(n) scanf("%%I64d",&n)
  16. #define PI acos(-1.0)
  17. #define LL long long
  18. #define MX 1000005
  19. #define MOD 1000000007
  20. typedef long long int ll;
  21. bool status[1100002];
  22. struct xy
  23. {
  24.   int x,y;
  25. }
  26. data[503];
  27. int par[503];
  28. int nd,st;
  29. struct xxx
  30. {
  31.     int u,v;
  32.     double c;
  33.     xxx(int x,int y,double e)
  34.     {
  35.         u=x;
  36.         v=y;
  37.         c=e;
  38.     }
  39. };
  40. vector<xxx>vec;
  41. double ans;
  42. int find(int i)
  43. {
  44.   if(i==par[i]) return i;
  45.   else return par[i]=find(par[i]);
  46. }
  47. void ini(void)
  48. {
  49.     for(int i=1;i<=nd;i++)
  50.     par[i]=i;
  51. }
  52. void link(int x,int y)
  53. {
  54.     if(x>y)
  55.     {
  56.         par[x]=y;
  57.     }
  58.     else
  59.     {
  60.         par[y]=x;
  61.     }
  62. }
  63. void calculate_distance(void)
  64. {
  65.     for(int i=1;i<=nd;i++)
  66.     {
  67.         for(int j=i+1;j<=nd;j++)
  68.         {
  69.             double dis=((data[i].x-data[j].x)*(data[i].x-data[j].x))+
  70.             ((data[i].y-data[j].y)*(data[i].y-data[j].y));
  71.             dis=sqrt(dis);
  72.             vec.push_back(xxx(i,j,dis));
  73.         }
  74.     }
  75. }
  76. int comp(xxx a,xxx b)
  77. {
  78.     return a.c<b.c;
  79. }
  80. void MST(void)
  81. {
  82.     sort(vec.begin(),vec.end(),comp);
  83.     int x,y,i,cnt=0;
  84.     ans=0.0;
  85.     for(i=0;i<vec.size() && cnt<nd-1;i++)
  86.     {
  87.         x=find(vec[i].u);
  88.         y=find(vec[i].v);
  89.         if(x!=y)
  90.         {
  91.             cnt++;
  92.             link(x,y);
  93.             if(vec[i].c>ans)
  94.             ans=vec[i].c;
  95.         }
  96.         if(cnt==nd-st) break;
  97.     }
  98. }
  99. int main()
  100. {
  101.    int i,j,k,x,y,cs,test;
  102.    cin>>test;
  103.    while(test--)
  104.    {
  105.        cin>>st>>nd;
  106.        ini();
  107.        vec.clear();
  108.        for(i=1;i<=nd;i++)
  109.        cin>>data[i].x>>data[i].y;
  110.        calculate_distance();
  111.        MST();
  112.        printf("%.2lf\n",ans);
  113.    }
  114. }
  115.  
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
1
2 4
0 100
0 300
0 600
150 750
stdout
copy 
212.13
https://ideone.com/83RSLd
language:
C++14 (clang 8.0)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!