function lab2
clear
X =input('請輸入X(X為n*2的矩陣):\n') ;
num=size(X,1);
for i=1:1:num
    for j=1:1:num
        D(i,j)=((X(i,1)-X(j,1))^2+(X(i,2)-X(j,2))^2)^(1/2);
    end
end
D
for i=1:1:num
    dlast=-1;dmin=100;sign=0;
    for j=1:1:num
        dmin=100;
        for k=1:1:num
            if D(i,k)>dlast && D(i,k)<dmin
                dmin=D(i,k);
                sign=k;
            end
        end
        M(sign,i)=j-1;dlast=dmin;
    end
end
M
for i=1:1:num
    for j=1:1:num
        if i==j
            L(i,j)=2*num;
        else
            L(i,j)=M(i,j)+M(j,i)-2;
        end
    end
end
L
c=0;C=[];A=[];
Lmin=100;s=0;
for i=1:1:num
    if L(1,i)<Lmin
        s=i;Lmin=L(1,i);
    end
end
c=1;A(1)=0;
W(1,1)=1;W(1,2)=s;C(1)=2;
plot([X(1,1),X(s,1)],[X(1,2),X(s,2)],'-.d');hold on;
if L(1,s)>A(1)
    A(1)=L(1,s);
end
for i=2:1:num
    Lmin=100;s=0;
    for j=1:1:num
        if L(i,j)<Lmin
            s=j;Lmin=L(i,j);
        end
    end
    ais=0;
    for k=1:1:c
        ai=0;as=0;
        for l=1:1:C(k)
            if W(k,l)==i
                ai=1;
                if L(i,s)>A(k)
                    A(k)=L(i,s);
                end
            end
            if W(k,l)==s
                as=1;
                if L(i,s)>A(k)
                    A(k)=L(i,s);
                end
            end
        end
        if ai==1&&as==0
            C(k)=C(k)+1;W(k,C(k))=s;ais=1;
            plot([X(i,1),X(s,1)],[X(i,2),X(s,2)],'-.d');
            
        else if ai==0&&as==1
                C(k)=C(k)+1;W(k,C(k))=i;ais=1;
                plot([X(i,1),X(s,1)],[X(i,2),X(s,2)],'-.d');
            end
        end
        if ai==1&&as==1
            ais=1;
            plot([X(i,1),X(s,1)],[X(i,2),X(s,2)],'-.d');
        end
    end
    if ais==0
        c=c+1;C(c)=2;
        W(c,1)=i;W(c,2)=s;
        plot([X(i,1),X(s,1)],[X(i,2),X(s,2)],'-.d');
        A(c)=L(i,s);
    end
end
over=0;R=[];
while over==0
    for i=1:1:c-1 
        for j=i+1:1:c
            rmin=100;
            for k=1:1:C(i)
                for l=1:1:C(j)
                    if L(W(i,k),W(j,l))<rmin
                        rmin=L(W(i,k),W(j,l));
                    end
                end
            end
            R(i,j)=rmin;
        end
    end
    i=1;
    bing=0;
    while i<=c&&bing==0
        j=i+1;
        while j<=c&&bing==0
            if R(i,j)<A(i)||R(i,j)<A(j)
                bing=1;p=i;q=j;
            end
            j=j+1;
        end
        i=i+1;
    end
    if bing==1
        m=0;n=0;
        rmin=100;
        for k=1:1:C(p)
            for l=k:1:C(q)
                if L(W(p,k),W(q,l))<rmin
                    rmin=L(W(p,k),W(q,l));m=W(p,k);n=W(q,l);
                end
            end
        end
        plot([X(m,1),X(n,1)],[X(m,2),X(n,2)],'-.d');
        for i=1:1:C(q)
            W(p,i+C(p))=W(q,i);
        end
        C(p)=C(p)+C(q);
        A(p)=max(A(p),A(q));
        for k=q:1:c-1
            W(k,:)=W(k+1,:);C(k)=C(k+1);A(k)=A(k+1);
        end
        c=c-1;
    else if bing==0
            over=1;
        end
    end
end