#include "stdio.h" 
#include "math.h" 
void main() 
{ 
long x[21]={0},y[21]={0},d[191]={0},e[191]={0},g[41]={0},s[42]={0}; 
int i,j,h=1,l,o,m,n=0,p,q=3,r=0; 
int flag; 
double k,a[21]={0},b[21][21]={0},c[21][21]={0},f[191]={0}; 
char ch; 

printf("                            C-W算法求解TSP問題 \n\n\n"); 
    printf("請輸入坐標（20個以內），坐標之間用空格隔開，按回車鍵結束輸入：\n"); 
    
re:scanf("%d,%d",&x[h],&y[h]); 
  ch=getchar(); 
  if(ch!='\n') 
  { h++; 
    goto re; 
  }     
  
    for(i=1;i <h+1;i++) 
  a[i]=sqrt(x[i]*x[i]+y[i]*y[i]);  
  
for(i=1;i <h;i++) 
  { 
  for(j=i+1;j <h+1;j++) 
    {  n++; 
      b[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])); 
      c[i][j]=a[i]+a[j]-b[i][j]; 
      d[n]=i; 
      e[n]=j; 
      f[n]=c[i][j]; 
    } 
  }  
  
for(i=1;i <n;i++) 
  { flag=0; 
    for(j=1;j <n+1-i;j++) 
        if(f[j]>f[j+1]) 
          { k=f[j];f[j]=f[j+1];f[j+1]=k; 
          l=d[j];d[j]=d[j+1];d[j+1]=l; 
            o=e[j];e[j]=e[j+1];e[j+1]=o; 
            flag=1; 
          } 
    if(flag==0) 
      break; 
  }  

printf("\n"); 
    printf("節約值排序：\n"); 
for(i=n;i>0;i--) 
  { if(f[i]!=0) 
    printf("%lf(%ld,%ld)--(%ld,%ld)\n",f[i],x[d[i]],y[d[i]],x[e[i]],y[e[i]]); 
  }  
  
g[1]=d[n]; 
g[2]=e[n]; 
    
for(m=1;m <h;m++) 
  { 
  for(j=n-1;j>0;j--) 
    {  p=0; 
    for(i=1;i <41;i++) 
      {  
        if(d[j]==g[i])  
          p=p+1; 
        if(e[j]==g[i]) 
          p=p+1; 
      } 
    if(p==1) 
      { g[q]=d[j]; 
        g[q+1]=e[j]; 
      } 
      if(p==1) 
        break; 
    } 
    q=q+2; 
  }  
    
    
    printf("\n選出連接點：\n"); 
    for(i=1;i <41;i=i+2) 
      { if(g[i]!=0) 
        { 
        printf("(%ld,%ld)--(%ld,%ld)\n",x[g[i]],y[g[i]],x[g[i+1]],y[g[i+1]]); 
          r=r+2; 
        } 
      } 
        
  s[21]=g[1]; 
  s[22]=g[2]; 
  
      for(i=3;i <r;i=i+2) 
          for(j=1;j <42;j++) 
            { 
            if(g[i]==s[j]) 
              { 
              if(s[j-1]==0) 
                s[j-1]=g[i+1]; 
              else 
                s[j+1]=g[i+1]; 
                break; 
              } 
              
            if(g[i+1]==s[j]) 
              { 
              if(s[j-1]==0) 
                s[j-1]=g[i]; 
              else 
                s[j+1]=g[i]; 
                break; 
              } 
            } 
            
        printf("\n旅行商路線：\n");  
        printf("(0,0)--");  
      for(i=1;i <42;i++)  
        { 
        if(s[i]!=0)  
          printf("(%ld,%ld)--",x[s[i]],y[s[i]]); 
        } 
        printf("(0,0)"); 
        getchar(); 
}