Problem 438 The Circumference of the Circle，求圓周長

過三點求圓
這是國中數學裡以三點形成一個圓，此三點不在一條線上。
分兩次任取兩點，畫出兩條線段，再求這兩條線段的中垂線相交於一點，就是圓心，這在平面上作圖是容易的事，但是要寫入程式中，必須將所有的公式算出來。
三點座標分別為 (x1,y1), (x2,y2), (x3,y3)。
首先算出任兩個線段的斜率，例如點1連點2線段(L_12)的斜率為(y2-y1)/(x2-x1)，點1連點3線段(L_13)的斜率為(y3-y1)/(x3-x1)，與這兩個線段垂直的斜率為

m_12 = -(x2-x1)/(y2-y1)，
m_13 = -(x3-x1)/(y3-y1)，

這兩個中垂線段分別通過L_12和L_13的中點 ((x1+x2)/2, (y1+y2)/2) 和 ((x1+x3)/2, (y1+y3)/2)

c12x = (x1+x2)/2;
c12y = (y1+y2)/2;
c13x = (x1+x3)/2;
c13y = (y1+y3)/2;

所以這兩個中垂線的公式為

y = m_12*(x - c12x) + c12y
y = m_13*(x - c13x) + c13y

因此求解這兩條線的交點，即得圓心座標(cx, cy)。解二元一次方程式，答案如下

cx = (c13y-c12y-m_13*c13x+m_12*c12x)/(m_12-m_13)
cy = m_12*(cx-c12x)+c12y

而半徑就是圓心到三點的距離

r = sqrt((x1-cx)*(x1-cx)+(y1-cy)*(y1-cy))

解題的C語言重點部分如下，必須注意取出任兩點線段時，如為垂直，會導致斜率的分母為零，簡單的方法，就是再取一點與其中一點對調。

if (y2==y1)
{
    temp = x1;
    x1 = x3;
    x3 = temp;
    temp = y1;
    y1 = y3;
    y3 = temp;
}
m_12 = -(x2-x1)/(y2-y1);
if (y3==y1)
{
    temp = x1;
    x1 = x2;
    x2 = temp;
    temp = y1;
    y1 = y2;
    y2 = temp;
}        
m_13 = -(x3-x1)/(y3-y1);
c12x = (x1+x2)/2;
c12y = (y1+y2)/2;
c13x = (x1+x3)/2;
c13y = (y1+y3)/2;
cx = (c13y-c12y-m_13*c13x+m_12*c12x)/(m_12-m_13);
cy = m_12*(cx-c12x)+c12y;
r = dist(cx,cy,x1,y1);
printf("%.2f\n", 2*PI*r);

這個題目的重點是要能化成公式，以套入C語言來解題。
注意：必須處理特殊狀況，例如分母為零時。
p438題目連結
回ACM題庫目錄
回首頁