2008年11月13日 星期四

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

2008年11月1日 星期六

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