ゆらのふなびと

競プロ, Python, C++

複素数をつかって三角形の外心を求める

「幾何の問題は複素数を使うと実装が軽くなるよ!」という噂を聞いたのでPythonでやってみた。

今回使うのはこちらの問題↓↓

Circumscribed Circle of a Triangle | Aizu Online Judge

三角形の頂点の座標が与えられるので、外接円の中心と半径を答えよという問題。

三角形の外心の公式(複素数ver.)は次のサイトを参考にしました。

http://www.compassare.org/cpx-pl.html

(内心の公式もあるので使えるかも。垂心については「単位円に内接する」という条件がついていることに注意)

ということで実装ドーン!!!

N = int(input()) #num of testcase
for i in range(N):
    #one test case
    x1, y1, x2, y2, x3, y3 = map(float, input().split())
    #vertices
    a = complex(x1, y1)
    b = complex(x2, y2)
    c = complex(x3, y3)
    #make c = 0 by parallel transformation
    a -= c
    b -= c
    
    z0 = abs(a)**2 * b - abs(b)**2 * a
    z0 /= a.conjugate() * b - a * b.conjugate()
    
    #inverse parallel transformation
    z = z0 + c
    zx = "{0:.3f}".format(z.real)
    zy = "{0:.3f}".format(z.imag)
    r  = "{0:.3f}".format(abs(z0))
    print(zx, zy, r)

公式は頂点の1つが0のとき、残り2つの座標を使って求めるものだったので、そのように平行移動しています。

半径は平行移動先の中心(z0)の絶対値、答える座標はz0を平行移動で戻したものですね。

注意点をいくつか。

  • comple(x, y) で x + y*j を得られる
  • complex.real はメンバ変数(?)でありメソッドではない。つまり()はいらない
  • 複素数の変数にも+, - などの演算子が使える

そのうち競プロの問題で使えたらいいな。




(追記)

複素数と平面幾何 - 純粋関数型雑記帳

↑他にも交点求めたりとか、ぶっちゃけなんでもできるらしい。