AOJ 0010 Circumscribed Circle of a Triangle

問題概要

平面上の3点(x₁, y₁), (x₂, y₂), (x₃, y₃)が与えられたとき、それらを頂点とした三角形の外接円の中心座標と半径を求めよ。

制約

• -100 ≤ x₁, y₁, x₂, y₂, x₃, y₃ ≤ 100
• データセットの数 ≤ 20

解法

点1と点2の垂直二等分線、点2と点3の垂直二等分線を求め、それぞれl₁, l₂とする。
l₁とl₂の交点が外接円の中心座標となる。

また、半径は、中心座標からいずれかの点への距離である。

コード

#include <iostream>
#include <cmath>
 
using namespace std;
 
#define EPS (1e-5)
#define equals(a, b) (fabs(a - b) < EPS)
 
struct Point {
    double x, y;
 
    Point(){}
    Point(double x, double y) : x(x), y(y) {}
 
    Point operator + (const Point &p) const {
        return Point(x + p.x, y + p.y);
    }
 
    Point operator - (const Point &p) const {
        return Point(x - p.x, y - p.y);
    }
     
    Point operator * (const double &k) const {
        return Point(x * k, y * k);
    }
};
 
typedef Point Vector;
 
double dot(const Point &a, const Point &b)
{
    return a.x * b.x + a.y * b.y;
}
 
double cross(const Point &a, const Point &b)
{
    return a.x * b.y - b.x * a.y;
}
 
double norm(const Point &p)
{
    return dot(p, p);
} 
 
double abs(const Point &p)
{
    return sqrt(norm(p));
}
 
struct Line {
    Point s, t;
    Line(){}
    Line(Point s, Point t) : s(s), t(t) {}
};
 
Line getPerpendicularBisector(const Point &a, const Point &b)
{
    double cx = (a.x + b.x) / 2.0;
    double cy = (a.y + b.y) / 2.0;
    Point p = Point(cx + (a.y - b.y), cy + (b.x - a.x));
    return Line(Point(cx, cy),p);
}
 
Point crosspointLL(const Line &a, const Line &b)
{
    Vector va = a.t - a.s, vb = b.t - b.s;
    double d = cross(vb, va);
    if (abs(d) < EPS) return b.s;
    return a.s+va*cross(vb, b.t - a.s) * (1.0 / d);
}
 
int main()
{
    Point p[3];
    int N;
    cin >> N;
    while (N--) {
        for (int i = 0; i < 3; i++) {
            cin >> p[i].x >> p[i].y;
        }
        Line l[2];
        for (int i = 0; i < 2; i++) {
            l[i] = getPerpendicularBisector(p[i], p[i+1]);
        }
        Point c = crosspointLL(l[0], l[1]);
        double r = abs(c - p[0]);
        printf("%.3f %.3f %.3f\n", c.x, c.y, r);
    }
    return 0;
}