Problem 190 Circle Through Three Points，通過三點的圓

ACM 190 的題目是讀取三個點的座標，利用這三個點算出圓的公式。
假設讀取點為 P1、P2、P3，在這裡的算法是求出兩條分別垂直於P1P2連線與P1P3連線的直線方程式，L12與L13，如上圖所示。

求L12時，先求出P1P2連線的中點，再求出L12的斜率。

中點座標分別為 C12x = (P1x+P2x)/2, C12y = (P1y+P2y)/2，

斜率為 m12 = -(P2x-P1x)/(P2y-P1y)。

所以 L12 的直線公式為 y = m12 * (x - C12x) + C12y

L13 的計算方式類似，L13 的直線公式為 y = m13 * (x - C13x) + C13y

這時就可以求L12與L13兩條線的交點，這個交點 C 就是圓心。

求解L12與L13 聯立方程式，得圓心座標(x, y)

x = (C13y-C12y-m13*C13x+m12*C12x) / (m12-m13)
y = m12 * (x-C12x) + C12y

半徑 r 為 (x,y) 到 (P1x,P1y) 的距離。
這部份的C語言程式碼如下：

c12x = (x1+x2)/2;
c12y = (y1+y2)/2;
c13x = (x1+x3)/2;
c13y = (y1+y3)/2;
cx = (c13y-c12y-m13*c13x+m12*c12x)/(m12-m13);
cy = m12*(cx-c12x)+c12y;
r = dist(cx,cy,x1,y1);
printf("(x %c %.3f)^2 + ", cx>=0?'-':'+', cx>=0?cx:-cx);
printf("(y %c %.3f)^2 = %.3f^2\n", cy>=0?'-':'+', cy>=0?cy:-cy, r);
printf("x^2 + y^2 %c %.3fx", cx>=0?'-':'+', cx>=0?2*cx:-2*cx);
printf(" %c %.3fy", cy>=0?'-':'+', cy>=0?2*cy:-2*cy);
e1 = cx*cx + cy*cy -r*r;
printf(" %c %.3f = 0\n\n", e1>=0?'+':'-', e1>=0?e1:-e1);

要特別注意的是斜率的計算，因為遇到P1P2或P1P3為水平線時，其垂直線的斜率會有除以零的錯誤，所以這裡用了交換的方式，換成另外一個點。m12的C語言程式碼如下，m13也用類似的方法。

if (y2==y1)
{
    temp = x1;
    x1 = x3;
    x3 = temp;
    temp = y1;
    y1 = y3;
    y3 = temp;
}
m12 = -(x2-x1)/(y2-y1);

p190題目連結
回ACM題庫目錄
回首頁

Problem 216 Getting in Line，連線作業

這個問題有點像是銷售員旅行問題(Travelling Salesman Problem, TSP)，但是不用回到出發點，也就是不用將最後一點與第一點再連接，解決 TSP 的方法很多，這裡的題目特別點出最多只有八台電腦要連結，所以可能的解答只有 8! = 40320 種方法，所以最簡單的方式就是將每個可能的答案都算出來，將最小的解答顯示出來，就OK啦。
在這裡，我又用到了回溯的方法，在C語言主程式中的初始呼叫如下：

for (i=0;i<n;i++)
{
    computer[0] = i;
    makeConn(0);
}

然後，makeConn(0)會去呼叫makeConn(1)，呼叫前先將連線的 computer[1]也設定下一個，因為不能重複，所以要用 i_in_conn 來處理，等到了makeConn(7)，表示八台電腦都設完了，就計算一下連線長度，再將最小的解答儲存，這樣就可以了。 makeConn 回溯的程式碼如下，這裡的 minlength, opttour, computer 都是全域變數：

void makeConn(int level)
{
    int i, j, i_in_conn;
    double len;
    if (level == n-1)
    {
        len = connLength(); /* your function to calculate the connection length */
        if (minlength > len)
        {
            minlength = len;
            for (j=0;j<n;j++)
                opttour[j] = computer[j];
        }
    }
    else
    {
        for (i=0;i<n;i++)
        {
            i_in_conn = 0;
            for (j=0;j<=level;j++)
                if (computer[j]==i)
                    i_in_conn = 1;
            if (!i_in_conn)
            {
                computer[level+1] = i;
                makeConn(level+1);
            }
        }
    }
}

p216題目連結
回ACM題庫目錄
回首頁