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

AOJ 0010

競技プログラミング

Circumscribed Circle of a Triangle | Aizu Online Judge

外接円の中心の座標を  \mathrm{O}(x, y) として,次の方程式を解く.

 \displaystyle (x-x_1)^2 + (y-y_1)^2 = (x-x_2)^2 + (y-y_2)^2 = (x-x_3)^2 + (y-y_3)^2

つまり,次のような連立方程式を解けばよい.

 \displaystyle \left\{ \begin{array}{l} (x-x_1)^2 + (y-y_1)^2 = (x-x_2)^2 + (y-y_2)^2 \\ (x-x_2)^2 + (y-y_2)^2 = (x-x_3)^2 + (y-y_3)^2 \end{array} \right.

解は次のようになる.

 \displaystyle x = \frac{1}{2} \frac{(y_3-y_2)(x_2^2-x_1^2+y_2^2-y_1^2) - (y_2-y_1)(x_3^2-x_2^2+y_3^2-y_2^2)}{(x_2-x_1)(y_3-y_2)-(y_2-y_1)(x_3-x_2)}

 \displaystyle y = \frac{1}{2} \frac{-(x_3-x_2)(x_2^2-x_1^2+y_2^2-y_1^2) + (x_2-x_1)(x_3^2-x_2^2+y_3^2-y_2^2)}{(x_2-x_1)(y_3-y_2)-(y_2-y_1)(x_3-x_2)}

外接円の半径  r は外接円の中心と 3 つのうちのひとつの点の Euclid 距離を求めればいい.

#include <iostream>
#include <array>
#include <cmath>
#include <iomanip>

using namespace std;

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; ++i) {
        array<pair<double, double>, 3> p;
        cin >> p[0].first >> p[0].second >> p[1].first >> p[1].second >> p[2].first >> p[2].second;

        pair<long double, long double> o(
                ((p[2].second - p[1].second) * (pow(p[1].first, 2.0) - pow(p[0].first, 2.0) + pow(p[1].second, 2.0) - pow(p[0].second, 2.0)) - (p[1].second - p[0].second) * (pow(p[2].first, 2.0) - pow(p[1].first, 2.0) + pow(p[2].second, 2.0) - pow(p[1].second, 2.0))) / (2.0 * ((p[1].first - p[0].first) * (p[2].second - p[1].second) - (p[1].second - p[0].second) * (p[2].first - p[1].first))),
                (- (p[2].first - p[1].first) * (pow(p[1].first, 2.0) - pow(p[0].first, 2.0) + pow(p[1].second, 2.0) - pow(p[0].second, 2.0)) + (p[1].first - p[0].first) * (pow(p[2].first, 2.0) - pow(p[1].first, 2.0) + pow(p[2].second, 2.0) - pow(p[1].second, 2.0))) / (2.0 * ((p[1].first - p[0].first) * (p[2].second - p[1].second) - (p[1].second - p[0].second) * (p[2].first - p[1].first)))
        );

        long double r = sqrt(pow(p[0].first - o.first, 2.0) + pow(p[0].second - o.second, 2.0));

        cout << fixed << setprecision(3) << o.first << " " << o.second << " " << r << endl;
    }

    return 0;
}