AOJ Course CGL_7_B: 内接円 (Incircle of a Triangle)

手持ちライブラリの組合せで内接円・外接円求めたりするの、結構楽しい！

• 問題へのリンク

問題概要

二次元平面上に 3 点 A, B, C が与えられる。三角形 ABC の内接円の中心の座標と、半径を求めよ。誤差は まで許容。

制約

• 座標値の絶対値

考えたこと

角 A, B の二等分線の交点を求めればよい。次のようにして求めた。

DD A = amp((c-a)/(b-a)), B = amp((a-b)/(c-b));
Line s(a, a+rot(b-a,A/2));
Line t(b, b+rot(c-b,B/2));

つまり、角 A の二等分線は

• 角度 A を求める ((c-a)/(b-a) の偏角)
• b - a を A/2 だけ回転させる

という方法で求めた。角 B の二等分線も同様。

こうして求めた 2 つの直線の交点が、内接円の中心 v となる。内接円の半径は

• v から辺 AB へ射影 (proj) した点 h を求め
• v と h との距離 abs(v - h) が答え

コード

#include <bits/stdc++.h>
using namespace std;

using DD = double;
const DD INF = 1LL<<60;      // to be set appropriately
const DD EPS = 1e-10;        // to be set appropriately
const DD PI = acosl(-1.0);
DD torad(int deg) {return (DD)(deg) * PI / 180;}
DD todeg(DD ang) {return ang * 180 / PI;}

/* Point */
struct Point {
    DD x, y;
    Point(DD x = 0.0, DD y = 0.0) : x(x), y(y) {}
    friend ostream& operator << (ostream &s, const Point &p) {return s << '(' << p.x << ", " << p.y << ')';}
};
inline Point operator + (const Point &p, const Point &q) {return Point(p.x + q.x, p.y + q.y);}
inline Point operator - (const Point &p, const Point &q) {return Point(p.x - q.x, p.y - q.y);}
inline Point operator * (const Point &p, DD a) {return Point(p.x * a, p.y * a);}
inline Point operator * (DD a, const Point &p) {return Point(a * p.x, a * p.y);}
inline Point operator * (const Point &p, const Point &q) {return Point(p.x * q.x - p.y * q.y, p.x * q.y + p.y * q.x);}
inline Point operator / (const Point &p, DD a) {return Point(p.x / a, p.y / a);}
inline Point conj(const Point &p) {return Point(p.x, -p.y);}
inline Point rot(const Point &p, DD ang) {return Point(cos(ang) * p.x - sin(ang) * p.y, sin(ang) * p.x + cos(ang) * p.y);}
inline Point rot90(const Point &p) {return Point(-p.y, p.x);}
inline DD cross(const Point &p, const Point &q) {return p.x * q.y - p.y * q.x;}
inline DD dot(const Point &p, const Point &q) {return p.x * q.x + p.y * q.y;}
inline DD norm(const Point &p) {return dot(p, p);}
inline DD abs(const Point &p) {return sqrt(dot(p, p));}
inline DD amp(const Point &p) {DD res = atan2(p.y, p.x); if (res < 0) res += PI*2; return res;}
inline bool eq(const Point &p, const Point &q) {return abs(p - q) < EPS;}
inline bool operator < (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x < q.x : p.y < q.y);}
inline bool operator > (const Point &p, const Point &q) {return (abs(p.x - q.x) > EPS ? p.x > q.x : p.y > q.y);}
inline Point operator / (const Point &p, const Point &q) {return p * conj(q) / norm(q);}

/* Line */
struct Line : vector<Point> {
    Line(Point a = Point(0.0, 0.0), Point b = Point(0.0, 0.0)) {
        this->push_back(a);
        this->push_back(b);
    }
    friend ostream& operator << (ostream &s, const Line &l) {return s << '{' << l[0] << ", " << l[1] << '}';}
};

/* Circle */
struct Circle : Point {
    DD r;
    Circle(Point p = Point(0.0, 0.0), DD r = 0.0) : Point(p), r(r) {}
    friend ostream& operator << (ostream &s, const Circle &c) {return s << '(' << c.x << ", " << c.y << ", " << c.r << ')';}
};

// projection
Point proj(const Point &p, const Line &l) {
    DD t = dot(p - l[0], l[1] - l[0]) / norm(l[1] - l[0]);
    return l[0] + (l[1] - l[0]) * t;
}

// crosspoint
vector<Point> crosspoint(const Line &l, const Line &m) {
    vector<Point> res;
    DD d = cross(m[1] - m[0], l[1] - l[0]);
    if (abs(d) < EPS) return vector<Point>();
    res.push_back(l[0] + (l[1] - l[0]) * cross(m[1] - m[0], m[1] - l[0]) / d);
    return res;
}

int main() {
    Point a, b, c;
    while (cin>>a.x>>a.y>>b.x>>b.y>>c.x>>c.y) {
        DD A = amp((c-a)/(b-a)), B = amp((a-b)/(c-b));
        Line s(a, a+rot(b-a,A/2));
        Line t(b, b+rot(c-b,B/2));
        auto v = crosspoint(s, t)[0];
        auto h = proj(v, Line(a,b));
        cout << fixed << setprecision(10);
        cout << v.x << " " << v.y << " " << abs(v - h) << endl;
    }
}