Circumscribed Circle of a Triangle(AOJ No.0010)

リポジトリ

Circumscribed Circle of a Triangle(AOJ No.0010)

• circumscribed circle
• central coordinate

頂点がが与えられたときの外接円の中心座標(外心)とその半径を求める

アルゴリズム

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

外接円の中心から三角形の頂点までの距離は等しい(=半径)なので、



(1)=(2) ... (A)
(1)=(3) ... (B)
を整理して連立方程式をとく

これをCramerの公式(Cramer's fomula)で解く。
半径はで求める(iはどれでもおｋ)

コード

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;
	}
}