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題庫目錄
回首頁