”C十十” 的ACM題目 緊急! Q438..

Question

Q438: The Circumference of the Circle
要計算一個圓的圓週長似乎是相當簡單的事，如果你知道直徑的話。但是如果你不知道直徑呢？

給你不共線的三個點的座標，你的任務是算出通過這三個點的唯一圓的週長是多少。

Input

每組測試資料一列，含有6個實數x1,y1,x2,y2,x3,y3，分別代表三個點的座標（此三個點不共線）。通過這三個點的唯一圓的直徑不會超過1百萬。

Output

對每一組測試資料，輸出通過這三個點的唯一圓的週長是多少，請輸出到小數點後2位。

圓週率PI的值大約是 3.141592653589793

Sample Input

0.0 -0.5 0.5 0.0 0.0 0.5
0.0 0.0 0.0 1.0 1.0 1.0
5.0 5.0 5.0 7.0 4.0 6.0
0.0 0.0 -1.0 7.0 7.0 7.0
50.0 50.0 50.0 70.0 40.0 60.0
0.0 0.0 10.0 0.0 20.0 1.0
0.0 -500000.0 500000.0 0.0 0.0 500000.0
Sample Output

3.14
4.44
6.28
31.42
62.83
632.24
3141592.65

Answer 1

這是 Borland C
所以請自行做適度的修改
七組測試的數值也在裡面
也請自行修改
#include
#include
main()
{
double pi, x0, y0, x1, y1, x2, y2, x, y, r, m1, c1, m2, c2;
pi = 3.141592653589793;
x0 = 0.0; y0 = -0.5; x1 = 0.5; y1 = 0.0; x2 = 0.0; y2 = 0.5;
x0 = 0.0; y0 = 0.0; x1 = 0.0; y1 = 1.0; x2 = 1.0; y2 = 1.0;
x0 = 5.0; y0 = 5.0; x1 = 5.0; y1 = 7.0; x2 = 4.0; y2 = 6.0;
x0 = 0.0; y0 = 0.0; x1 = -1.0; y1 = 7.0; x2 = 7.0; y2 = 7.0;
x0 = 50.0; y0 = 50.0; x1 = 50.0; y1 = 70.0; x2 = 40.0; y2 = 60.0;
x0 = 0.0; y0 = 0.0; x1 = 10.0; y1 = 0.0; x2 = 20.0; y2 = 1.0;
x0 = 0.0; y0 =-500000.0; x1 = 500000.0; y1 = 0.0; x2 = 0.0; y2 = 500000.0;
x = 0;
if (y0 == y1)
{
x = (x0+x1)/2;
}
else
{
m1 = (x1-x0)/(y0-y1);
c1 = (y1+y0)/2 - m1*(x1+x0)/2;
}
if (y0 == y2)
{
x = (x0+x2)/2;
}
else
{
m2 = (x2-x0)/(y0-y2);
c2 = (y2+y0)/2 - m2*(x2+x0)/2;
}
if (x == 0) x = (c2-c1)/(m1-m2);
if (y0 == y1)
y = m2*x + c2;
else
y = m1*x + c1;
r = sqrt((x-x0)*(x-x0) + (y-y0)*(y-y0));
printf("通過三點 (%4.1f,%4.1f) (%4.1f,%4.1f) (%4.1f,%4.1f) 的圓的週長是 %4.2f\n",
x0, y0, x1, y1, x2, y2, 2*pi*r);
return;
}
如果有問題, 請來函討論. 不然, 我可能會錯失你再補充的疑點.

Answer 2

這個原理可以用幾何學來回答.
假設圓上不共線三點A, B, C,
則任兩點形成之線段的垂直平分線會通過圓心,
所以
(1) 求AB線段中點坐標H1
(2) 求BC線段中點坐標H2
(3) 求與AB線段垂直之斜率m1
(4) 求與BC線段垂直之斜率m2
(5) 定義L1為通過H1, 斜率m1之直線 (即AB之中垂線)
定義L2為通過H2, 斜率m2之直線 (即 BC之中垂線)
求L1, L2之交點 O點坐標, 此即該圓之圓心
(6) 求圓心O到圓上任意點(以A為例)距離, 此即為半徑 r = OA
(7) 求周長=2*pi*r

H1=(H1x, H1y)=((Ax+Bx)/2, (Ay+By)/2)
m1= (B1x - A1x) / (A1y - B1y)
L1 equation: (x-H1x)=m1(y-H1y)
即 x=m1*y+H1x-m1*H1y
同理
L2 equation : x=m2*y+H2x-m2*H2y
求L1, L2交點O(Ox,Oy)同時滿足L1, L2
Ox=Ox 所以 m1*Oy + H1x-m1*H1y=m2*Oy+H2x-m2*H2y
Oy=(H2x-H1x+m1*H1y-m2*H2y)/(m1-m2)
代回, Ox=m1*Oy+H1x-m1*H1y
r=sqrt((Ox-Ax)^2+(Oy-Ay)^2)
圓周=2*pi*r

公式推導你可能要自己重推一次, 剛睡起不確定有沒不仔細...