This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ebi-fly13/icpc_library
#define PROBLEM \ "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/7/CGL_7_B" #define ERROR 0.0000001 #include "../../geometry/base_ld.hpp" #include "../../geometry/circle.hpp" #include "../../template/template.hpp" using namespace lib; int main() { std::cout << std::fixed << std::setprecision(15); auto input = [](vec &a) { ld x, y; std::cin >> x >> y; a = {x, y}; }; vec a, b, c; input(a); input(b); input(c); circle in = incircle_of_triangle(a, b, c); std::cout << in.c.real() << " " << in.c.imag() << " " << in.r << '\n'; }
#line 1 "test/geometry/Incircle_of_Triangle.test.cpp" #define PROBLEM \ "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/7/CGL_7_B" #define ERROR 0.0000001 #line 2 "geometry/base_ld.hpp" #line 2 "template/template.hpp" #include <bits/stdc++.h> #define rep(i, s, n) for (int i = (int)(s); i < (int)(n); i++) #define rrep(i, s, n) for (int i = (int)(n)-1; i >= (int)(s); i--) #define all(v) v.begin(), v.end() using ll = long long; using ld = long double; using ull = unsigned long long; template <typename T> bool chmin(T &a, const T &b) { if (a <= b) return false; a = b; return true; } template <typename T> bool chmax(T &a, const T &b) { if (a >= b) return false; a = b; return true; } namespace lib { using namespace std; } // namespace lib // using namespace lib; #line 4 "geometry/base_ld.hpp" namespace lib { using vec = complex<ld>; const ld PI = acos(-1); void ldout(int len = 20) { cout << fixed << setprecision(len); } int sgn(ld a, const ld eps = 1e-7) { return (a < -eps) ? -1 : (a > eps) ? 1 : 0; } bool same_vec(vec a, vec b) { a -= b; return sgn(a.real()) == 0 && sgn(a.imag()) == 0; } ld dot(const vec &a, const vec &b) { return (conj(a) * b).real(); } ld cross(const vec &a, const vec &b) { return (conj(a) * b).imag(); } int isp(const vec &a, const vec &b, const vec &c) { int cross_sgn = sgn(cross(b - a, c - a)); if (cross_sgn == 0) { if (sgn(dot(b - a, c - a)) < 0) return -2; if (sgn(dot(a - b, c - b)) < 0) return 2; } return cross_sgn; } vec rot90(const vec &a) { return {-a.imag(), a.real()}; } vec rot(const vec &a, ld rad) { return a * vec(cosl(rad), sinl(rad)); } bool comp_for_argument_sort(const vec &lhs, const vec &rhs) { // if (abs(arg(lhs)-arg(rhs)) < eps) return false; // need ? return arg(lhs) < arg(rhs); } } // namespace lib #line 2 "geometry/circle.hpp" #line 2 "geometry/line.hpp" #line 4 "geometry/line.hpp" namespace lib { struct line { vec a, b; }; vec proj(const line &l, const vec &p) { vec ab = l.b - l.a; return l.a + ab * (dot(ab, p - l.a) / norm(ab)); } vec refl(const line &l, const vec &p) { return proj(l, p) * ld(2) - p; } int intersection(const line &a, const line &b) { if (sgn(cross(a.b - a.a, b.a - b.b)) != 0) { if (sgn(dot(a.b - a.a, b.a - b.b)) == 0) { return 1; } return 0; } else if (sgn(cross(a.b - a.a, b.a - a.a)) != 0) { return 2; } else { return 3; } } ld dist(const line &a, const vec &p) { return abs(cross(p - a.a, a.b - a.a) / abs(a.b - a.a)); } vec cross_point(const line &a, const line &b) { assert(intersection(a, b) < 2); return a.a + (a.b - a.a) * cross(b.a - a.a, b.b - b.a) / cross(a.b - a.a, b.b - b.a); } } // namespace lib #line 5 "geometry/circle.hpp" namespace lib { struct circle { vec c; ld r; }; int intersection(const circle &c1, const circle &c2) { if (sgn(c1.c.real() - c2.c.real()) == 0 && sgn(c1.c.imag() - c2.c.imag()) == 0 && sgn(c1.r - c2.r) == 0) return 5; ld d = abs(c1.c - c2.c); ld r1 = c1.r; ld r2 = c2.r; if (r1 < r2) std::swap(r1, r2); if (sgn(d - (r1 + r2)) > 0) { return 4; } else if (sgn(d - (r1 + r2)) == 0) { return 3; } else if (sgn(d - r1 + r2) > 0) { return 2; } else if (sgn(d - r1 + r2) == 0) { return 1; } else return 0; } circle incircle_of_triangle(const vec &a, const vec &b, const vec &c) { ld A = abs(b - c), B = abs(c - a), C = abs(a - b); vec in = A * a + B * b + C * c; in /= A + B + C; ld r = abs(cross(in - a, b - a) / abs(b - a)); return {in, r}; } circle circumscribed_circle_of_triangle(const vec &a, const vec &b, const vec &c) { line p = {(a + b) / ld(2.0), (a + b) / ld(2.0) + rot90(b - a)}; line q = {(b + c) / ld(2.0), (b + c) / ld(2.0) + rot90(c - b)}; vec cross = cross_point(p, q); return {cross, abs(a - cross)}; } vector<vec> cross_point(const circle &c, const line &l) { vector<vec> ps; ld d = dist(l, c.c); if (sgn(d - c.r) == 0) ps.emplace_back(proj(l, c.c)); else if (sgn(d - c.r) < 0) { vec p = proj(l, c.c); vec v = l.b - l.a; v *= sqrt(max(c.r * c.r - d * d, ld(0))) / abs(v); ps.emplace_back(p + v); ps.emplace_back(p - v); } return ps; } vector<vec> cross_point(const circle &c1, const circle &c2) { vector<vec> ps; int cnt_tangent = intersection(c1, c2); if (cnt_tangent == 0 || cnt_tangent == 4) return {}; ld d = abs(c2.c - c1.c); ld x = (d * d + c1.r * c1.r - c2.r * c2.r) / (2 * d); vec p = c1.c + (c2.c - c1.c) * x / d; vec v = rot90(c2.c - c1.c); if (cnt_tangent == 1 || cnt_tangent == 3) ps.emplace_back(p); else { v *= sqrt(max(c1.r * c1.r - x * x, ld(0))) / abs(v); ps.emplace_back(p + v); ps.emplace_back(p - v); } return ps; } ld common_area(const circle &c1, const circle &c2) { int flag = intersection(c1, c2); if (flag == 3 || flag == 4) return 0.0; else if (flag == 0 || flag == 1 || flag == 5) { ld r = std::min(c1.r, c2.r); return PI * r * r; } else { ld d = abs(c1.c - c2.c); ld theta1 = c1.r * c1.r + d * d - c2.r * c2.r; theta1 /= 2.0 * c1.r * d; theta1 = acos(theta1); ld area1 = c1.r * c1.r * theta1 - c1.r * c1.r * sin(theta1 * 2) / 2.0; ld theta2 = c2.r * c2.r + d * d - c1.r * c1.r; theta2 /= 2.0 * c2.r * d; theta2 = acos(theta2); ld area2 = c2.r * c2.r * theta2 - c2.r * c2.r * sin(theta2 * 2) / 2.0; return area1 + area2; } } } // namespace lib #line 8 "test/geometry/Incircle_of_Triangle.test.cpp" using namespace lib; int main() { std::cout << std::fixed << std::setprecision(15); auto input = [](vec &a) { ld x, y; std::cin >> x >> y; a = {x, y}; }; vec a, b, c; input(a); input(b); input(c); circle in = incircle_of_triangle(a, b, c); std::cout << in.c.real() << " " << in.c.imag() << " " << in.r << '\n'; }