competitive-programing

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

View the Project on GitHub Astral-23/competitive-programing

:warning: icpc_Others/geometory/circles.cpp

Code

// https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all
// 7_A, 7_B, 7_C, 7_D, 7_E, 7_F, 7_G, 7_H, 7_I

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

using Point = complex<double>;
using Polygon = vector<Point>;

struct Line {
    Point a, b;
    Line(Point a, Point b) : a(a), b(b) {}
};

struct Segment : Line {
    Segment(Point a, Point b) : Line(a, b) {}
};

struct Circle {
    Point p;
    double r;
    Circle(Point p, double r) : p(p), r(r) {}
};

const double pi = acos(-1.0);
const double EPS = 1e-12;

// 内積
double dot(const Point &a, const Point &b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}

// 外積
double cross(const Point &a, const Point &b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

// 円の交差判定
int intersection_of_circle(const Circle &c1, const Circle &c2) {
    double d = abs(c1.p - c2.p);
    // 分離
    if (d > c1.r + c2.r + EPS) {
        return 4;
    }
    // 外接
    if (abs(d - c1.r - c2.r) < EPS) {
        return 3;
    }
    // 交差
    if (d < c1.r + c2.r - EPS && d > abs(c1.r - c2.r) + EPS) {
        return 2;
    }
    // 内接
    if (abs(d - abs(c1.r - c2.r)) < EPS) {
        return 1;
    }
    // 包含
    return 0;
}

// 内接円
Circle incircle(const Point &p1, const Point &p2, const Point &p3) {
    double d = abs((p1 - p2)) + abs(p2 - p3) + abs(p3 - p1);
    Point p = p1 + (abs(p3 - p1) / d) * (p2 - p1) + (abs(p2 - p1) / d) * (p3 - p1);
    double r = abs(cross(p2 - p1, p3 - p1)) / d;
    return Circle(p, r);
}

// 外接円
Circle circumscribed_circle(const Point &p1, const Point &p2, const Point &p3) {
    double a = abs(p1 - p2), b = abs(p2 - p3), c = abs(p3 - p1), S = abs(cross(p2 - p1, p3 - p1)) * 0.5;
    double cx = norm(p2 - p1) * (p3 - p1).imag() - norm(p3 - p1) * (p2 - p1).imag(), cy = norm(p3 - p1) * (p2 - p1).real() - norm(p2 - p1) * (p3 - p1).real();
    cx /= 2.0 * cross(p2 - p1, p3 - p1);
    cy /= 2.0 * cross(p2 - p1, p3 - p1);
    Point p = p1 + Point(cx, cy);
    double r = a * b * c / (4.0 * S);
    return Circle(p, r);
}

// 直線と点の距離
double distance(const Line s, const Point &p) {
    double t = dot(p - s.a, s.b - s.a) / norm(s.b - s.a);
    Point proj = Point(s.a.real() + t * (s.b - s.a).real(), s.a.imag() + t * (s.b - s.a).imag());
    return abs(p - proj);
}

// 直線 l に対する点 p の射影
Point projection(const Line l, const Point &p) {
    double t = dot(p - l.a, l.b - l.a) / norm(l.b - l.a);
    return Point(l.a.real() + t * (l.b - l.a).real(), l.a.imag() + t * (l.b - l.a).imag());
}

// 円と直線の交点
vector<Point> cross_points(Circle c, Line l) {
    Point proj = projection(l, c.p);
    double d = abs(proj - c.p);
    if (d > c.r + EPS) {
        return {};
    }
    if (abs(c.r - abs(proj - c.p)) < EPS) {
        return {proj};
    }
    double s = sqrt(c.r * c.r - norm(proj - c.p));
    return {proj - (s / abs(l.b - l.a)) * (l.b - l.a), proj + (s / abs(l.b - l.a)) * (l.b - l.a)};
}

// 円と円の交点
vector<Point> cross_points(Circle c1, Circle c2) {
    int t = intersection_of_circle(c1, c2);
    if (t == 0 || t == 4) {
        return {};
    }
    if (t == 3) {
        return {c1.p + (c1.r / (c1.r + c2.r)) * (c2.p - c1.p)};
    }
    if (t == 1) {
        if (c1.r > c2.r) return {(-c2.r / abs(c1.r - c2.r)) * c1.p + (c1.r / abs(c1.r - c2.r)) * c2.p};
        return {(c2.r / abs(c1.r - c2.r)) * c1.p + (-c1.r / abs(c1.r - c2.r)) * c2.p};
    }
    double d = abs(c1.p - c2.p);
    double s = (c1.r * c1.r - c2.r * c2.r + d * d) / (2.0 * d);
    Point p = c1.p + (s / d) * (c2.p - c1.p);
    return {p - (sqrt(c1.r * c1.r - s * s) / d) * Point((c2.p - c1.p).imag(), -(c2.p - c1.p).real()), p + (sqrt(c1.r * c1.r - s * s) / d) * Point((c2.p - c1.p).imag(), -(c2.p - c1.p).real())};
}

// 円の接線
vector<Point> tangent(Circle c, Point p) {
    return cross_points(c, Circle(p, sqrt(norm(c.p - p) - c.r * c.r)));
}

// 円の共通接線
vector<Point> common_tangent(Circle c1, Circle c2) {
    double d = norm(c1.p - c2.p);
    double d1 = d - (c1.r + c2.r) * (c1.r + c2.r) + c2.r * c2.r;
    vector<Point> ps;
    if (d1 > -EPS) {
        d1 = sqrt(max(d1, 0.0));
        vector<Point> ps1 = cross_points(c1, Circle(c2.p, d1));
        for (auto p : ps1) ps.push_back(p);
    }
    double d2 = d - (c1.r - c2.r) * (c1.r - c2.r) + c2.r * c2.r;
    if (d2 > -EPS) {
        d2 = sqrt(max(d2, 0.0));
        vector<Point> ps2 = cross_points(c1, Circle(c2.p, d2));
        for (auto p : ps2) ps.push_back(p);
    }
    return ps;
}

// 多角形の面積
double area(const Polygon &poly) {
    double ans = 0;
    int N = poly.size();
    for (int i = 0; i < N; i++) {
        ans += cross(poly[i], poly[(i + 1) % N]);
    }
    ans *= 0.5;
    return ans;
}

// 円の共通部分の面積
double area_of_intersection(Circle c1, Circle c2) {
    int t = intersection_of_circle(c1, c2);
    if (t >= 3) {
        return 0;
    }
    if (t <= 1) {
        return pi * min(c1.r, c2.r) * min(c1.r, c2.r);
    }
    vector<Point> ps = cross_points(c1, c2);
    double a1 = arg(ps[0] - c1.p) - arg(ps[1] - c1.p), a2 = arg(ps[1] - c2.p) - arg(ps[0] - c2.p);
    if (a1 < -EPS) a1 += 2.0 * pi;
    if (a2 < -EPS) a2 += 2.0 * pi;
    return (a1 / 2) * c1.r * c1.r + (a2 / 2) * c2.r * c2.r - abs(area({ps[0], c1.p, ps[1], c2.p}));
}

// p0 から p1 へ結んだベクトルから見た p2 の位置
int counter_clockwise(const Point &p2, Point p0, Point p1) {
    // 反時計回り
    if (cross(p1 - p0, p2 - p0) > EPS) {
        return 1;
    }
    // 時計回り
    if (cross(p1 - p0, p2 - p0) < -EPS) {
        return -1;
    }
    // p2, p0, p1 の順で同一直線上
    if (dot(p1 - p0, p2 - p0) < -EPS) {
        return 2;
    }
    // p0, p1, p2 の順で同一直線上
    if (dot(p1 - p0, p2 - p0) > norm(p1 - p0) + EPS) {
        return -2;
    }
    // p2 は p0 と p1 を結ぶ線分上
    return 0;
}

int is_contained(const Point p, const Polygon poly) {
    int N = poly.size();
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (counter_clockwise(p, poly[i], poly[(i + 1) % N]) == 0) {
            return 1;
        }
        Point a = poly[i], b = poly[(i + 1) % N];
        if (a.imag() > b.imag()) swap(a, b);
        if (p.imag() < b.imag() + EPS && p.imag() > a.imag() + EPS && counter_clockwise(p, a, b) < 0) {
            cnt++;
        }
    }
    if (cnt % 2 == 0) return 0;
    else return 2;
}

// 円と線分の交点
vector<Point> cross_points(Circle c, Line l) {
    Point proj = projection(l, c.p);
    double d = abs(proj - c.p);
    if (d > c.r + EPS) {
        return {};
    }
    if (abs(c.r - abs(proj - c.p)) < EPS) {
        if (counter_clockwise(proj, l.a, l.b) == 0) return {proj};
        else return {};
    }
    double s = sqrt(c.r * c.r - norm(proj - c.p));
    Point p1 = proj - (s / abs(l.b - l.a)) * (l.b - l.a), p2 = proj + (s / abs(l.b - l.a)) * (l.b - l.a);
    vector<Point> ps;
    if (counter_clockwise(p1, l.a, l.b)) ps.push_back(p1);
    if (counter_clockwise(p2, l.a, l.b)) ps.push_back(p2);
    return ps;
}

// 円と多角形の共通部分の面積
double area_of_intersection(Circle c, Polygon poly) {
    int N = poly.size();
}

int main() {
    cout << fixed << setprecision(15);
    int N, R;
    cin >> N >> R;
    Polygon poly(N);
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        poly[i] = Point(x, y);
    }
    cout << area_of_intersection(Circle(Point(0, 0), R), poly) << "\n";
}
#line 1 "icpc_Others/geometory/circles.cpp"
// https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all
// 7_A, 7_B, 7_C, 7_D, 7_E, 7_F, 7_G, 7_H, 7_I

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

using Point = complex<double>;
using Polygon = vector<Point>;

struct Line {
    Point a, b;
    Line(Point a, Point b) : a(a), b(b) {}
};

struct Segment : Line {
    Segment(Point a, Point b) : Line(a, b) {}
};

struct Circle {
    Point p;
    double r;
    Circle(Point p, double r) : p(p), r(r) {}
};

const double pi = acos(-1.0);
const double EPS = 1e-12;

// 内積
double dot(const Point &a, const Point &b) {
    return (a.real() * b.real() + a.imag() * b.imag());
}

// 外積
double cross(const Point &a, const Point &b) {
    return (a.real() * b.imag() - a.imag() * b.real());
}

// 円の交差判定
int intersection_of_circle(const Circle &c1, const Circle &c2) {
    double d = abs(c1.p - c2.p);
    // 分離
    if (d > c1.r + c2.r + EPS) {
        return 4;
    }
    // 外接
    if (abs(d - c1.r - c2.r) < EPS) {
        return 3;
    }
    // 交差
    if (d < c1.r + c2.r - EPS && d > abs(c1.r - c2.r) + EPS) {
        return 2;
    }
    // 内接
    if (abs(d - abs(c1.r - c2.r)) < EPS) {
        return 1;
    }
    // 包含
    return 0;
}

// 内接円
Circle incircle(const Point &p1, const Point &p2, const Point &p3) {
    double d = abs((p1 - p2)) + abs(p2 - p3) + abs(p3 - p1);
    Point p = p1 + (abs(p3 - p1) / d) * (p2 - p1) + (abs(p2 - p1) / d) * (p3 - p1);
    double r = abs(cross(p2 - p1, p3 - p1)) / d;
    return Circle(p, r);
}

// 外接円
Circle circumscribed_circle(const Point &p1, const Point &p2, const Point &p3) {
    double a = abs(p1 - p2), b = abs(p2 - p3), c = abs(p3 - p1), S = abs(cross(p2 - p1, p3 - p1)) * 0.5;
    double cx = norm(p2 - p1) * (p3 - p1).imag() - norm(p3 - p1) * (p2 - p1).imag(), cy = norm(p3 - p1) * (p2 - p1).real() - norm(p2 - p1) * (p3 - p1).real();
    cx /= 2.0 * cross(p2 - p1, p3 - p1);
    cy /= 2.0 * cross(p2 - p1, p3 - p1);
    Point p = p1 + Point(cx, cy);
    double r = a * b * c / (4.0 * S);
    return Circle(p, r);
}

// 直線と点の距離
double distance(const Line s, const Point &p) {
    double t = dot(p - s.a, s.b - s.a) / norm(s.b - s.a);
    Point proj = Point(s.a.real() + t * (s.b - s.a).real(), s.a.imag() + t * (s.b - s.a).imag());
    return abs(p - proj);
}

// 直線 l に対する点 p の射影
Point projection(const Line l, const Point &p) {
    double t = dot(p - l.a, l.b - l.a) / norm(l.b - l.a);
    return Point(l.a.real() + t * (l.b - l.a).real(), l.a.imag() + t * (l.b - l.a).imag());
}

// 円と直線の交点
vector<Point> cross_points(Circle c, Line l) {
    Point proj = projection(l, c.p);
    double d = abs(proj - c.p);
    if (d > c.r + EPS) {
        return {};
    }
    if (abs(c.r - abs(proj - c.p)) < EPS) {
        return {proj};
    }
    double s = sqrt(c.r * c.r - norm(proj - c.p));
    return {proj - (s / abs(l.b - l.a)) * (l.b - l.a), proj + (s / abs(l.b - l.a)) * (l.b - l.a)};
}

// 円と円の交点
vector<Point> cross_points(Circle c1, Circle c2) {
    int t = intersection_of_circle(c1, c2);
    if (t == 0 || t == 4) {
        return {};
    }
    if (t == 3) {
        return {c1.p + (c1.r / (c1.r + c2.r)) * (c2.p - c1.p)};
    }
    if (t == 1) {
        if (c1.r > c2.r) return {(-c2.r / abs(c1.r - c2.r)) * c1.p + (c1.r / abs(c1.r - c2.r)) * c2.p};
        return {(c2.r / abs(c1.r - c2.r)) * c1.p + (-c1.r / abs(c1.r - c2.r)) * c2.p};
    }
    double d = abs(c1.p - c2.p);
    double s = (c1.r * c1.r - c2.r * c2.r + d * d) / (2.0 * d);
    Point p = c1.p + (s / d) * (c2.p - c1.p);
    return {p - (sqrt(c1.r * c1.r - s * s) / d) * Point((c2.p - c1.p).imag(), -(c2.p - c1.p).real()), p + (sqrt(c1.r * c1.r - s * s) / d) * Point((c2.p - c1.p).imag(), -(c2.p - c1.p).real())};
}

// 円の接線
vector<Point> tangent(Circle c, Point p) {
    return cross_points(c, Circle(p, sqrt(norm(c.p - p) - c.r * c.r)));
}

// 円の共通接線
vector<Point> common_tangent(Circle c1, Circle c2) {
    double d = norm(c1.p - c2.p);
    double d1 = d - (c1.r + c2.r) * (c1.r + c2.r) + c2.r * c2.r;
    vector<Point> ps;
    if (d1 > -EPS) {
        d1 = sqrt(max(d1, 0.0));
        vector<Point> ps1 = cross_points(c1, Circle(c2.p, d1));
        for (auto p : ps1) ps.push_back(p);
    }
    double d2 = d - (c1.r - c2.r) * (c1.r - c2.r) + c2.r * c2.r;
    if (d2 > -EPS) {
        d2 = sqrt(max(d2, 0.0));
        vector<Point> ps2 = cross_points(c1, Circle(c2.p, d2));
        for (auto p : ps2) ps.push_back(p);
    }
    return ps;
}

// 多角形の面積
double area(const Polygon &poly) {
    double ans = 0;
    int N = poly.size();
    for (int i = 0; i < N; i++) {
        ans += cross(poly[i], poly[(i + 1) % N]);
    }
    ans *= 0.5;
    return ans;
}

// 円の共通部分の面積
double area_of_intersection(Circle c1, Circle c2) {
    int t = intersection_of_circle(c1, c2);
    if (t >= 3) {
        return 0;
    }
    if (t <= 1) {
        return pi * min(c1.r, c2.r) * min(c1.r, c2.r);
    }
    vector<Point> ps = cross_points(c1, c2);
    double a1 = arg(ps[0] - c1.p) - arg(ps[1] - c1.p), a2 = arg(ps[1] - c2.p) - arg(ps[0] - c2.p);
    if (a1 < -EPS) a1 += 2.0 * pi;
    if (a2 < -EPS) a2 += 2.0 * pi;
    return (a1 / 2) * c1.r * c1.r + (a2 / 2) * c2.r * c2.r - abs(area({ps[0], c1.p, ps[1], c2.p}));
}

// p0 から p1 へ結んだベクトルから見た p2 の位置
int counter_clockwise(const Point &p2, Point p0, Point p1) {
    // 反時計回り
    if (cross(p1 - p0, p2 - p0) > EPS) {
        return 1;
    }
    // 時計回り
    if (cross(p1 - p0, p2 - p0) < -EPS) {
        return -1;
    }
    // p2, p0, p1 の順で同一直線上
    if (dot(p1 - p0, p2 - p0) < -EPS) {
        return 2;
    }
    // p0, p1, p2 の順で同一直線上
    if (dot(p1 - p0, p2 - p0) > norm(p1 - p0) + EPS) {
        return -2;
    }
    // p2 は p0 と p1 を結ぶ線分上
    return 0;
}

int is_contained(const Point p, const Polygon poly) {
    int N = poly.size();
    int cnt = 0;
    for (int i = 0; i < N; i++) {
        if (counter_clockwise(p, poly[i], poly[(i + 1) % N]) == 0) {
            return 1;
        }
        Point a = poly[i], b = poly[(i + 1) % N];
        if (a.imag() > b.imag()) swap(a, b);
        if (p.imag() < b.imag() + EPS && p.imag() > a.imag() + EPS && counter_clockwise(p, a, b) < 0) {
            cnt++;
        }
    }
    if (cnt % 2 == 0) return 0;
    else return 2;
}

// 円と線分の交点
vector<Point> cross_points(Circle c, Line l) {
    Point proj = projection(l, c.p);
    double d = abs(proj - c.p);
    if (d > c.r + EPS) {
        return {};
    }
    if (abs(c.r - abs(proj - c.p)) < EPS) {
        if (counter_clockwise(proj, l.a, l.b) == 0) return {proj};
        else return {};
    }
    double s = sqrt(c.r * c.r - norm(proj - c.p));
    Point p1 = proj - (s / abs(l.b - l.a)) * (l.b - l.a), p2 = proj + (s / abs(l.b - l.a)) * (l.b - l.a);
    vector<Point> ps;
    if (counter_clockwise(p1, l.a, l.b)) ps.push_back(p1);
    if (counter_clockwise(p2, l.a, l.b)) ps.push_back(p2);
    return ps;
}

// 円と多角形の共通部分の面積
double area_of_intersection(Circle c, Polygon poly) {
    int N = poly.size();
}

int main() {
    cout << fixed << setprecision(15);
    int N, R;
    cin >> N >> R;
    Polygon poly(N);
    for (int i = 0; i < N; i++) {
        int x, y;
        cin >> x >> y;
        poly[i] = Point(x, y);
    }
    cout << area_of_intersection(Circle(Point(0, 0), R), poly) << "\n";
}
Back to top page