#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>

using namespace std;

const double EPS = 1e-9;
const double PI = acos(-1);

int sign(double x) {
    if (fabs(x) < EPS) {
        return 0;
    } else if (x > 0) {
        return 1;
    } else {
        return -1;
    }
}

int dcmp(double x, double y) {
    return sign(x - y);
}

struct Vector;
typedef Vector Point;
struct Circle;
struct Polygon;

struct Vector {
    double x;
    double y;

    explicit Vector(double x = 0, double y = 0);

    Vector operator+(const Vector &rhs) const;
    Vector operator-() const;
    Vector operator-(const Vector &rhs) const;
    Vector operator*(double d) const;
    Vector operator/(double d) const;
    double operator*(const Vector &rhs) const;
    double operator^(const Vector &rhs) const;

    bool operator==(const Vector &rhs) const;
    bool operator!=(const Vector &rhs) const;
    bool operator<(const Vector &rhs) const;
    bool operator>(const Vector &rhs) const;
    bool operator<=(const Vector &rhs) const;
    bool operator>=(const Vector &rhs) const;

    friend std::ostream &operator<<(std::ostream &os, const Vector &vector);

    double dot(const Vector &rhs) const;
    double cross(const Vector &rhs) const;
    double length() const;
    double length2() const;
    double angle() const;
    double angle(const Vector &rhs) const;
    Vector rotate(double rad) const;
    Vector rotate90() const;
    Vector rotate90R() const;
    Vector normal() const;
    Vector truncate(double d) const;
    double getDistanceTo(const Point &p) const;

    static bool cmpByAngle(const Vector &a, const Vector &b);
};

struct Line {
    Point a;
    Point b;

    explicit Line(double x1 = 0, double y1 = 0, double x2 = 0, double y2 = 0);
    explicit Line(const Point &a = Point(), const Point &b = Point());

    double getDistanceTo(const Point &p) const;
    Point getIntersection(const Line &rhs) const;
    Point getProjection(const Point &p) const;
    Point getReflection(const Point &p) const;
    bool contains(const Point &p) const;
    bool intersects(const Line &rhs) const;
    bool parallels(const Line &rhs) const;
    bool isPerpendicularTo(const Line &rhs) const;
};

struct Segment {
    Point a;
    Point b;

    explicit Segment(double x1 = 0, double y1 = 0, double x2 = 0, double y2 = 0);
    explicit Segment(const Point &a = Point(), const Point &b = Point());

    double length() const;
    bool contains(const Point &p, bool containsEndPoints = true) const;
    bool intersects(const Segment &rhs, bool containsEndPoints = true) const;
    bool intersects(const Line &rhs, bool containsEndPoints = true) const;
    Point getIntersection(const Segment &rhs) const;
    double getDistanceTo(const Point &p) const;
    double getDistanceTo(const Segment &rhs) const;
};

struct Circle {
    Point center;
    double r;

    enum class ContainsPoint {
        OUT, ONLINE, IN
    };

    enum class IntersectsLine {
        NOT_CROSS,
        TANGENT,
        INTERSECT
    };

    enum class IntersectsCircle {
        NOT_CROSS,
        CIRCUMSCRIBED,
        INTERSECT,
        INSCRIBED,
        INCLUDED
    };

    explicit Circle(double x, double y, double r);
    explicit Circle(const Point &center = Point(), double r = 0);
    Circle(const Point &a, const Point &b, const Point &c, bool isExt = true);

    bool operator==(const Circle &rhs) const;
    bool operator!=(const Circle &rhs) const;

    double area() const;
    double circumference() const;
    Point point(double a) const;
    ContainsPoint contains(const Point &p) const;
    IntersectsLine intersects(const Line &line) const;
    IntersectsCircle intersects(const Circle &rhs) const;
    std::vector<Point> getIntersections(const Line &rhs) const;
    std::vector<Point> getIntersections(const Segment &rhs) const;
    std::vector<Point> getIntersections(const Circle &rhs) const;
    std::vector<Point> getIntersections(const Polygon &rhs) const;
    std::vector<Point> getTangentPoints(const Point &p) const;
    std::vector<Line> getInTangents(const Circle &rhs) const;
    std::vector<Line> getExTangents(const Circle &rhs) const;
    double getDistanceTo(const Circle &rhs) const;
    double getAreaOfOverlap(const Point &a, const Point &b) const;
    double getAreaOfOverlap(const Polygon &rhs) const;

    static std::vector<Circle> getCircles(const Point &a, const Point &b, double r);
    static std::vector<Circle> getCircles(const Line &u, const Point &p, double r);
    static std::vector<Circle> getCircles(const Line &u, const Line &v, double r);
    static std::vector<Circle> getCircles(const Circle &c1, const Circle &c2, double r);
};

struct Polygon {
    std::vector<Point> points;

    enum class ContainsPoint {
        OUT, ONLINE, ON_VERTEX, IN
    };


    explicit Polygon(const std::vector<Point> &points = std::vector<Point>(0));

    Point &operator[](int index);

    int size() const;
    double area() const;
    double circumference() const;
    ContainsPoint contains(const Point &p) const;
    Polygon cutBy(const Line &line) const;
    std::vector<Point> getIntersections(const Circle &rhs) const;
    double getAreaOfOverlap(const Circle &rhs) const;
};

Vector::Vector(double x, double y) : x(x), y(y) {}

Vector Vector::operator+(const Vector &rhs) const {
    return Vector(x + rhs.x, y + rhs.y);
}

Vector Vector::operator-() const {
    return Vector(-x, -y);
}

Vector Vector::operator-(const Vector &rhs) const {
    return *this + -rhs;
}

Vector Vector::operator*(double d) const {
    return Vector(x * d, y * d);
}

Vector Vector::operator/(double d) const {
    return *this * (1 / d);
}

double Vector::operator*(const Vector &rhs) const {
    return x * rhs.x + y * rhs.y;
}

double Vector::operator^(const Vector &rhs) const {
    return x * rhs.y - rhs.x * y;
}

bool Vector::operator==(const Vector &rhs) const {
    return dcmp(x, rhs.x) == 0 && dcmp(y, rhs.y) == 0;
}

bool Vector::operator!=(const Vector &rhs) const {
    return !(rhs == *this);
}

bool Vector::operator<(const Vector &rhs) const {
    if (dcmp(x, rhs.x) != 0) {
        return dcmp(x, rhs.x) < 0;
    } else {
        return dcmp(y, rhs.y) < 0;
    }
}

bool Vector::operator>(const Vector &rhs) const {
    return rhs < *this;
}

bool Vector::operator<=(const Vector &rhs) const {
    return !(rhs < *this);
}

bool Vector::operator>=(const Vector &rhs) const {
    return !(*this < rhs);
}

std::ostream &operator<<(std::ostream &os, const Vector &vector) {
    os << "(" << vector.x << "," << vector.y << ")";
    return os;
}

double Vector::dot(const Vector &rhs) const {
    return *this * rhs;
}

double Vector::cross(const Vector &rhs) const {
    return *this ^ rhs;
}

double Vector::length() const {
    return sqrt(*this * *this);
}

double Vector::length2() const {
    return *this * *this;
}

double Vector::angle() const {
    return atan2(y, x);
}

double Vector::angle(const Vector &rhs) const {
    return acos((*this * rhs) / length() / rhs.length());
}

Vector Vector::rotate(double rad) const {
    // Rotate counter-clockwise
    return Vector(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
}

Vector Vector::rotate90() const {
    return Vector(-y, x);
}

Vector Vector::rotate90R() const {
    return Vector(y, -x);
}

Vector Vector::normal() const {
    double l = length();
    return Vector(-y / l, x / l);
}

double Vector::getDistanceTo(const Point &p) const {
    return sqrt(pow(x - p.x, 2) + pow(y - p.y, 2));
}

bool Vector::cmpByAngle(const Vector &a, const Vector &b) {
    return dcmp(a.angle(), b.angle()) < 0;
}

Vector Vector::truncate(double d) const {
    double l = length();
    if (sign(l) == 0) {
        return *this;
    }
    d /= l;
    return Vector(x * d, y * d);
}

Line::Line(double x1, double y1, double x2, double y2) : a(x1, y1), b(x2, y2) {}

Line::Line(const Point &a, const Point &b) : a(a), b(b) {}

double Line::getDistanceTo(const Point &p) const {
    const Vector &v1 = b - a;
    const Vector &v2 = p - a;
    return fabs(v1 ^ v2 / v1.length());
}

Point Line::getIntersection(const Line &rhs) const {
    if (!intersects(rhs)) {
        return Point();
    }
    Vector u = a - rhs.a;
    Vector v = b - a;
    Vector w = rhs.b - rhs.a;
    double t = (w ^ u) / (v ^ w);
    return a + v * t;
}

Point Line::getProjection(const Point &p) const {
    const Vector &v = b - a;
    return a + v * (v * (p - a) / (v * v));
}

Point Line::getReflection(const Point &p) const {
    return getProjection(p) * 2 - p;
}

bool Line::contains(const Point &p) const {
    Point p1 = a;
    Point p2 = b;
    if (p1 == p) {
        p1 = p1 + (p2 - p1) * 2;
    } else if (p2 == p) {
        p2 = p2 + (p1 - p2) * 2;
    }
    return sign((p2 - p) ^ (p1 - p)) == 0;
}

bool Line::intersects(const Line &rhs) const {
    return sign((a - b) ^ (rhs.a - rhs.b)) != 0;
}

bool Line::parallels(const Line &rhs) const {
    return !intersects(rhs);
}

bool Line::isPerpendicularTo(const Line &rhs) const {
    return sign((b - a) * (rhs.b - rhs.a)) == 0;
}

Segment::Segment(double x1, double y1, double x2, double y2) : a(x1, y1), b(x2, y2) {}

Segment::Segment(const Point &a, const Point &b) : a(a), b(b) {}

double Segment::length() const {
    return a.getDistanceTo(b);
}

bool Segment::contains(const Point &p, bool containsEndPoints) const {
    const Vector &u = a - p;
    const Vector &v = b - p;
    return sign(u ^ v) == 0 && (containsEndPoints ? sign(u * v) <= 0 : sign(u * v) < 0);
}

bool Segment::intersects(const Segment &rhs, bool containsEndPoints) const {
    const Vector &u = b - a;
    const Vector &v = rhs.b - rhs.a;
    double c1 = u ^(rhs.a - a);
    double c2 = u ^(rhs.b - a);
    double c3 = v ^(a - rhs.a);
    double c4 = v ^(b - rhs.a);
    if (containsEndPoints && (!sign(c1) || !sign(c2) || !sign(c3) || !sign(c4))) {
        return contains(rhs.a) || contains(rhs.b) || rhs.contains(a) || rhs.contains(b);
    }
    return sign(c1) * sign(c2) < 0 && sign(c3) * sign(c4) < 0;
}

bool Segment::intersects(const Line &rhs, bool containsEndPoints) const {
    if (containsEndPoints && (rhs.contains(a) || rhs.contains(b))) {
        return true;
    }
    Vector v1 = a - rhs.getProjection(a);
    Vector v2 = b - rhs.getProjection(b);
    double d = v1 * v2;
    if (sign(d) < 0) {
        return true;
    }
    return sign(d) == 0 && (rhs.contains(a) || rhs.contains(b));
}

Point Segment::getIntersection(const Segment &rhs) const {
    if (!intersects(rhs)) {
        return Point();
    }
    const Point &p = Line(a, b).getIntersection(Line(rhs.a, rhs.b));
    return contains(p) ? p : Point();
}

double Segment::getDistanceTo(const Point &p) const {
    if (a == b) {
        return a.getDistanceTo(p);
    }
    const Vector &v1 = b - a;
    const Vector &v2 = p - a;
    const Vector &v3 = p - b;
    if (sign(v1 * v2) < 0) {
        return v2.length();
    } else if (sign(v1 * v3) > 0) {
        return v3.length();
    } else {
        return Line(a, b).getDistanceTo(p);
    }
}

double Segment::getDistanceTo(const Segment &rhs) const {
    if (intersects(rhs)) {
        return 0;
    } else {
        return std::min(std::min(rhs.getDistanceTo(a), rhs.getDistanceTo(b)), std::min(getDistanceTo(rhs.a), getDistanceTo(rhs.b)));
    }
}

Circle::Circle(double x, double y, double r) : center(x, y), r(r) {}

Circle::Circle(const Point &center, double r) : center(center), r(r) {}

Circle::Circle(const Point &a, const Point &b, const Point &c, bool isExt) {
    if (isExt) {
        // Circumscribed circle
        Line u((a + b) / 2, ((a + b) / 2) + ((b - a).rotate90()));
        Line v((b + c) / 2, ((b + c) / 2) + ((c - b).rotate90()));
        center = u.getIntersection(v);
        r = center.getDistanceTo(a);
    } else {
        // Inscribed circle
        double m = (b - a).angle();
        double n = (c - a).angle();
        Line u(a, a + Point(cos((n + m) / 2), sin((n + m) / 2)));
        m = (a - b).angle();
        n = (c - b).angle();
        Line v(b, b + Point(cos((n + m) / 2), sin((n + m) / 2)));
        center = u.getIntersection(v);
        r = Line(a, b).getDistanceTo(center);
    }
}

bool Circle::operator==(const Circle &rhs) const {
    return center == rhs.center && dcmp(r, rhs.r) == 0;
}

bool Circle::operator!=(const Circle &rhs) const {
    return !(rhs == *this);
}

Circle::ContainsPoint Circle::contains(const Point &p) const {
    double d = center.getDistanceTo(p);
    if (dcmp(r, d) < 0) {
        return ContainsPoint::OUT;
    } else if (dcmp(r, d) == 0) {
        return ContainsPoint::ONLINE;
    } else {
        return ContainsPoint::IN;
    }
}

Circle::IntersectsLine Circle::intersects(const Line &line) const {
    double d = line.getDistanceTo(center);
    int res = dcmp(d, r);
    if (res == 0) {
        return IntersectsLine::TANGENT;
    } else if (res > 0) {
        return IntersectsLine::NOT_CROSS;
    } else {
        return IntersectsLine::INTERSECT;
    }
}

Circle::IntersectsCircle Circle::intersects(const Circle &rhs) const {
    double d = getDistanceTo(rhs);
    if (dcmp(r + rhs.r, d) < 0) {
        return IntersectsCircle::NOT_CROSS;
    } else if (dcmp(r + rhs.r, d) == 0) {
        return IntersectsCircle::CIRCUMSCRIBED;
    } else if (dcmp(fabs(r - rhs.r), d) == 0) {
        return IntersectsCircle::INSCRIBED;
    } else if (dcmp(fabs(r - rhs.r), d) > 0) {
        return IntersectsCircle::INCLUDED;
    } else {
        return IntersectsCircle::INTERSECT;
    }
}

double Circle::getDistanceTo(const Circle &rhs) const {
    return center.getDistanceTo(rhs.center);
}

Point Circle::point(double a) const {
    return Point(center.x + cos(a) * r, center.y + sin(a) * r);
}

std::vector<Point> Circle::getIntersections(const Line &rhs) const {
    std::vector<Point> res;
    switch (intersects(rhs)) {
        case IntersectsLine::INTERSECT: {
            Point u = rhs.getProjection(center);
            Vector v = (rhs.b - rhs.a);
            v = v / v.length() * (sqrt(pow(r, 2) - pow(u.getDistanceTo(center), 2)));
            res.push_back(u + v);
            res.push_back(u - v);
            break;
        }
        case IntersectsLine::TANGENT: {
            res.push_back(rhs.getProjection(center));
            break;
        }
        case IntersectsLine::NOT_CROSS: {
            break;
        }
    }
    return res;
}

std::vector<Point> Circle::getIntersections(const Segment &rhs) const {
    std::vector<Point> res;
    const std::vector<Point> &points = getIntersections(Line(rhs.a, rhs.b));
    if (points.size() == 1) {
        if (rhs.contains(points.back())) { res.push_back(points.back()); }
        if (points.size() == 2) {
            if (rhs.contains(points.front())) { res.push_back(points.front()); }
        }
    }
    return res;
}

std::vector<Point> Circle::getIntersections(const Circle &rhs) const {
    std::vector<Point> res;
    double d = getDistanceTo(rhs);
    if (sign(d) == 0) {
        return res;
    } else if (dcmp(r + rhs.r, d) < 0) {
        return res;
    } else if (dcmp(fabs(r - rhs.r), d) > 0) {
        return res;
    }

    double a = (rhs.center - center).angle();
    double da = acos((r * r + d * d - rhs.r * rhs.r) / (2 * r * d));
    Point p1 = point(a - da);
    Point p2 = point(a + da);
    res.push_back(p1);
    if (p1 != p2) {
        res.push_back(p2);
    }
    return res;
}

std::vector<Point> Circle::getIntersections(const Polygon &rhs) const {
    return rhs.getIntersections(*this);
}

double Circle::area() const {
    return PI * r * r;
}

double Circle::circumference() const {
    return 2 * PI * r;
}

std::vector<Point> Circle::getTangentPoints(const Point &p) const {
    std::vector<Point> res;
    double d = center.getDistanceTo(p);
    switch (contains(p)) {
        case ContainsPoint::IN:
            return res;
        case ContainsPoint::ONLINE:
            res.push_back(p);
            return res;
        default:
            break;
    }
    double base = (p - center).angle();
    double angle = acos(r / d);
    res.push_back(point(base + angle));
    res.push_back(point(base - angle));
    return res;
}

std::vector<Line> Circle::getInTangents(const Circle &rhs) const {
    std::vector<Line> res;
    const Point &p = (center * rhs.r + rhs.center * r) / (r + rhs.r);
    const std::vector<Point> &vec1 = getTangentPoints(p);
    const std::vector<Point> &vec2 = rhs.getTangentPoints(p);
    if (!vec1.empty() && !vec2.empty()) {
        res.emplace_back(vec1.front(), vec2.front());
        res.emplace_back(vec1.back(), vec2.back());
    }
    return res;
}

std::vector<Line> Circle::getExTangents(const Circle &rhs) const {
    std::vector<Line> res;
    if (dcmp(r, rhs.r) == 0) {
        Vector dir = rhs.center - center;
        dir = (dir * (r / dir.length())).rotate90();
        res.emplace_back(center + dir, rhs.center + dir);
        res.emplace_back(center - dir, rhs.center - dir);
    } else {
        const Point &p = (center * -rhs.r + rhs.center * r) / (r - rhs.r);
        std::vector<Point> vec1 = getTangentPoints(p);
        std::vector<Point> vec2 = rhs.getTangentPoints(p);
        if (!vec1.empty() && !vec2.empty()) {
            res.emplace_back(vec1.front(), vec2.front());
            res.emplace_back(vec1.back(), vec2.back());
        }
    }
    return res;
}

double Circle::getAreaOfOverlap(const Point &a, const Point &b) const {
    // Get area of the circle overlapping with triangle OAB
    if (sign((center - a) ^ (center - b)) == 0) {
        return 0;
    }
    Line line(a, b);
    Point p[5];
    Point p1, p2;
    int len = 0;
    p[len++] = a;
    const std::vector<Point> &points = getIntersections(line);
    if (points.size() == 2) {
        p[1] = points.front();
        p[2] = points.back();
        if (sign((a - p[1]) * (b - p[1])) < 0) { p[len++] = p[1]; }
        if (sign((a - p[2]) * (b - p[2])) < 0) { p[len++] = p[2]; }
    }
    p[len++] = b;
    if (len == 4 && sign((p[0] - p[1]) * (p[2] - p[1])) > 0) {
        std::swap(p[1], p[2]);
    }

    double res = 0;
    for (int i = 0; i < len - 1; i++) {
        if (contains(p[i]) == ContainsPoint::OUT || contains(p[i + 1]) == ContainsPoint::OUT) {
            double angle = (p[i] - center).angle(p[i + 1] - center);
            res += r * r * angle / 2;
        } else {
            res += fabs((p[i] - center) ^ (p[i + 1] - center)) / 2;
        }
    }
    return res;
}

double Circle::getAreaOfOverlap(const Polygon &rhs) const {
    return rhs.getAreaOfOverlap(*this);
}

std::vector<Circle> Circle::getCircles(const Point &a, const Point &b, double r) {
    // Get circles passing points a and b with radius r
    std::vector<Circle> res;
    Circle x(a, r);
    Circle y(b, r);
    const std::vector<Point> &points = x.getIntersections(y);
    if (points.empty()) {
        return res;
    }
    res.emplace_back(points.front(), r);
    if (points.front() != points.back()) {
        res.emplace_back(points.back(), r);
    }
    return res;
}

std::vector<Circle> Circle::getCircles(const Line &u, const Point &p, double r) {
    // Get circles tangent with line u and passing p and with radius r
    std::vector<Circle> res;
    double d = u.getDistanceTo(p);
    if (sign(d - 2 * r) > 0) {
        return res;
    } else if (sign(d) == 0) {
        res.emplace_back(p + ((u.b - u.a).rotate90().truncate(r)), r);
        res.emplace_back(p + ((u.b - u.a).rotate90R().truncate(r)), r);
        return res;
    }
    Line u1(u.a + (u.b - u.a).rotate90().truncate(r), u.b + (u.b - u.a).rotate90().truncate(r));
    Line u2(u.a + (u.b - u.a).rotate90R().truncate(r), u.b + (u.b - u.a).rotate90R().truncate(r));
    Circle c(p, r);
    std::vector<Point> points = c.getIntersections(u1);
    if (points.empty()) {
        points = c.getIntersections(u2);
    }
    res.emplace_back(points.front(), r);
    if (points.front() != points.back()) {
        res.emplace_back(points.back(), r);
    }
    return res;
}

std::vector<Circle> Circle::getCircles(const Line &u, const Line &v, double r) {
    // Get 4 circles tangent with lines u and v and with radius r
    std::vector<Circle> res = std::vector<Circle>();
    if (!u.intersects(v)) {
        return res;
    }
    Line u1(u.a + (u.b - u.a).rotate90().truncate(r), u.b + (u.b - u.a).rotate90().truncate(r));
    Line u2(u.a + (u.b - u.a).rotate90R().truncate(r), u.b + (u.b - u.a).rotate90R().truncate(r));
    Line v1(v.a + (v.b - v.a).rotate90().truncate(r), v.b + (v.b - v.a).rotate90().truncate(r));
    Line v2(v.a + (v.b - v.a).rotate90R().truncate(r), v.b + (v.b - v.a).rotate90R().truncate(r));
    res.emplace_back(u1.getIntersection(v1), r);
    res.emplace_back(u1.getIntersection(v2), r);
    res.emplace_back(u2.getIntersection(v1), r);
    res.emplace_back(u2.getIntersection(v2), r);
    return res;
}

std::vector<Circle> Circle::getCircles(const Circle &c1, const Circle &c2, double r) {
    // Get circles tangent with circles c1 and c2, where c1 does not intersect with c2
    std::vector<Circle> res;
    Circle x(c1.center, r + c1.r);
    Circle y(c2.center, r + c2.r);
    const std::vector<Point> &points = x.getIntersections(y);
    if (!points.empty()) {
        res.emplace_back(points.front(), r);
        if (points.front() != points.back()) {
            res.emplace_back(points.back(), r);
        }
    }
    return res;
}

Polygon::Polygon(const std::vector<Point> &points) : points(points) {}

Point &Polygon::operator[](const int index) {
    return points[index];
}

int Polygon::size() const {
    return points.size();
}

double Polygon::area() const {
    if (points.size() < 3) {
        return 0;
    }
    double sum = points.back() ^points.front();
    for (int i = 0; i < (int) points.size() - 1; i++) {
        sum += points[i] ^ points[i + 1];
    }
    return sum / 2;
}

double Polygon::circumference() const {
    if (points.size() < 3) {
        return 0;
    }
    double sum = (points.back() - points.front()).length();
    for (int i = 0; i < (int) points.size() - 1; i++) {
        sum += (points[i] - points[i + 1]).length();
    }
    return sum;
}

Polygon::ContainsPoint Polygon::contains(const Point &p) const {
    Segment s0(p, p + Vector(1e10, 0));
    int sum = 0;
    for (int i = 0; i < points.size(); i++) {
        Point u = points[i];
        Point v = points[(i + 1) % points.size()];
        const Segment &s = Segment(u, v);
        if (u == p || v == p) {
            return ContainsPoint::ON_VERTEX;
        }
        if (s.contains(p)) {
            return ContainsPoint::ONLINE;
        }
        if (dcmp(u.y, v.y) <= 0) {
            std::swap(u, v);
        }
        if (dcmp(p.y, u.y) > 0 || dcmp(p.y, v.y) <= 0) {
            continue;
        }
        sum += s0.intersects(s) ? 1 : 0;
    }
    return (sum & 1) ? ContainsPoint::IN : ContainsPoint::OUT;

//    Another solution, using area (only for CONVEX)
//    for (int i = 0; i < points.size(); i++) {
//        if (Segment(points[i], points[(i + 1) % points.size()]).contains(rhs)) {
//            return ContainsPoint::ONLINE;
//        }
//    }
//    double sum = 0;
//    for (int i = 0; i < points.size(); i++) {
//        sum += fabs((points[i] - rhs) ^ (points[(i + 1) % points.size()] - rhs));
//    }
//    sum /= 2;
//    printf("sum, area: %.5f %.5f\n", sum, area());
//    return dcmp(sum, area()) == 0 ? ContainsPoint::IN : ContainsPoint::OUT;
}

Polygon Polygon::cutBy(const Line &line) const {
    // Only for CONVEX
    // Left side of the line
    Polygon res;
    for (int i = 0; i < points.size(); i++) {
        int j = (i + 1) % points.size();
        int d1 = sign((line.b - line.a) ^ (points[i] - line.a));
        int d2 = sign((line.b - line.a) ^ (points[j] - line.a));
        if (d1 >= 0) {
            res.points.push_back(points[i]);
        }
        if (d1 * d2 < 0) {
            res.points.push_back(line.getIntersection(Line(points[i], points[j])));
        }
    }
    return res;
}

std::vector<Point> Polygon::getIntersections(const Circle &rhs) const {
    std::vector<Point> res;
    for (int i = 0; i < points.size(); i++) {
        int j = (i + 1) % points.size();
        const std::vector<Point> &p = rhs.getIntersections(Segment(i, j));
        res.insert(res.end(), p.begin(), p.end());
    }
    sort(res.begin(), res.end());
    res.erase(unique(res.begin(), res.end()), res.end());
    return res;
}

double Polygon::getAreaOfOverlap(const Circle &rhs) const {
    double sum = 0;
    for (int i = 0; i < points.size(); i++) {
        int j = (i + 1) % points.size();
        if (sign((points[j] - rhs.center) ^ (points[i] - rhs.center)) >= 0) {
            sum += rhs.getAreaOfOverlap(points[i], points[j]);
        } else {
            sum -= rhs.getAreaOfOverlap(points[i], points[j]);
        }
    }
    return fabs(sum);
}


int main() {
//    freopen("data.in", "r", stdin);

    double x, y, r;
    int n;
    while (~scanf("%d%lf", &n, &r)) {
        Circle circle(0, 0, r);
        vector<Point> points;
        points.reserve(n);
        for (int i = 0; i < n; i++) {
            scanf("%lf%lf", &x, &y);
            points.emplace_back(x, y);
        }
        Polygon polygon(points);
        printf("%.10f\n", polygon.getAreaOfOverlap(circle));
    }
    return 0;
}



Measured memory_bytes: 3464