icpc_library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub ebi-fly13/icpc_library

:heavy_check_mark: test/geometry/Common_Area_Circles.test.cpp

Depends on

Code

#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/7/CGL_7_I"
#define ERROR 0.00000001

#include "../../geometry/base_ld.hpp"
#include "../../geometry/circle.hpp"
#include "../../template/template.hpp"

using namespace lib;

namespace ebi {

void main_() {
    circle c1, c2;
    auto input = [](circle &c) -> void {
        ld x, y, r;
        std::cin >> x >> y >> r;
        c.c = {x, y};
        c.r = r;
    };
    input(c1);
    input(c2);
    std::cout << common_area(c1, c2) << '\n';
}

}  // namespace ebi

int main() {
    std::cout << std::fixed << std::setprecision(15);
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ebi::main_();
}
#line 1 "test/geometry/Common_Area_Circles.test.cpp"
#define PROBLEM \
    "https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/7/CGL_7_I"
#define ERROR 0.00000001

#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/Common_Area_Circles.test.cpp"

using namespace lib;

namespace ebi {

void main_() {
    circle c1, c2;
    auto input = [](circle &c) -> void {
        ld x, y, r;
        std::cin >> x >> y >> r;
        c.c = {x, y};
        c.r = r;
    };
    input(c1);
    input(c2);
    std::cout << common_area(c1, c2) << '\n';
}

}  // namespace ebi

int main() {
    std::cout << std::fixed << std::setprecision(15);
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    ebi::main_();
}
Back to top page