読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

Circumscribed Circle of a Triangle(AOJ No.0010)

リポジトリ

Circumscribed Circle of a Triangle(AOJ No.0010)

頂点が \vec{p_1 }=(x_1 , y_1 ), \vec{p_2}=(x_2 , y_2 ), \vec{p_3}=(x_3 , y_3 )が与えられたときの外接円の中心座標 \vec{p}=(p_x, p_y)(外心)とその半径 rを求める

アルゴリズム

外心の性質
△ABCの辺BC,CA,ABの垂直二等分線は,外心で交わる
ということを利用して、解くこともできるが少々めんどくさい。

外接円の中心から三角形の頂点までの距離は等しい(=半径)なので、
 ||\vec{p}-\vec{p_1}||^2 \cdots(1)
 ||\vec{p}-\vec{p_2}||^2 \cdots(2)
 ||\vec{p}-\vec{p_3}||^2 \cdots(3)
(1)=(2) ... (A)
(1)=(3) ... (B)
を整理して連立方程式をとく
 \left \{ \begin{array} 2(x_1 - x_2 )p_x +2(y_1 - y_2 )p_y = x_1^2+y_1^2 - (x_2^2+y_2^2) \cdots(A') \\  2(x_1 - x_3 )p_x +2(y_1 - y_3 )p_y = x_1^2+y_1^2 - (x_3^2+y_3^2) \cdots(B') \end{array} \right.
これをCramerの公式(Cramer's fomula)で解く。
半径は ||\vec{p}-\vec{p_i}||で求める(iはどれでもおk)

コード

Simultaneous Equation(AOJ No.0004)の流用

import java.util.*;
public class aoj0010 {
	static final Scanner stdin = new Scanner(System.in);
	public static void main(String[] args) {
		double x1,x2,x3,y1,y2,y3;
		int n = stdin.nextInt();
		while( n-- > 0 ){
			x1 = stdin.nextDouble(); y1 = stdin.nextDouble();
			x2 = stdin.nextDouble(); y2 = stdin.nextDouble();
			x3 = stdin.nextDouble(); y3 = stdin.nextDouble();
			double[] ans = solve( 2*(x1-x2), 2*(y1-y2), x1*x1+y1*y1-(x2*x2+y2*y2), 2*(x1-x3), 2*(y1-y3), x1*x1+y1*y1-(x3*x3+y3*y3));
			System.out.printf("%.3f %.3f %.3f\n", ans[0], ans[1], Math.sqrt( Math.pow(ans[0]-x1, 2) + Math.pow(ans[1]-y1, 2) ) );
		}
	}
	static double[] solve(double a, double b, double c, double d, double e, double f){
		double[] ans = new double[2];
		ans[0] = (c*e - b*f) / (a*e - b*d) + 0.0; //+0.0 が無いと場合によっては
		ans[1] = (a*f - c*d) / (a*e - b*d) + 0.0; //printfしたとき -0.000と出てwrong answerになってしまう
		return ans;
	}
}