Problem: Find the area of intersection between a circle $c$ and a polygon $g$. The center coordinate of the circle is ($0, 0$).

The polygon $g$ is represented by a sequence of points $p_1$, $p_2$,..., $p_n$ where line segments connecting $p_i$ and $p_{i+1}$ ($1 \leq i \leq n−1$) are sides of the polygon. The line segment connecting $p_n$ and $p_1$ is also a side of the polygon.

Note that the polygon is not necessarily convex.

Constraints

* $3 \leq n \leq 100$
* $1 \leq r \leq 100$
* $-100 \leq x_i, y_i \leq 100$

Input

The input is given in the following format.

$n$ $r$
$x_1$ $y_1$
$x_2$ $y_2$
:
$x_n$ $y_n$


In the first line, an integer n representing the number of points in the polygon is given. The coordinate of a point $p_i$ is given by two integers $x_i$ and $y_i$. The coordinates of the points are given in the order of counter-clockwise visit of them. All input values are given in integers.

Output

Print the area of intersection in a line. The output values should be in a decimal fraction with an error less than 0.00001.

Examples

Input

3 5
1 1
4 1
5 5


Output

4.639858417607


Input

4 5
0 0
-3 -6
1 -3
5 -4


Output

11.787686807576

Solution (in CPP):

Solution:
#define _USE_MATH_DEFINES // for C++  

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

using namespace std;

const double eps = 1e-10;

class Point {
public:
    double x, y;
    Point(double _x = 0., double _y = 0.) : x(_x), y(_y) {}
};

istream& operator >> (istream& in, Point& P)
{
    in >> P.x >> P.y;
    return in;
}

ostream& operator << (ostream& out, const Point& P)
{
    out << P.x << " " << P.y;
    return out;
}

double Dist(const Point& P, const Point& Q)
{
    double dx = P.x - Q.x;
    double dy = P.y - Q.y;
    return sqrt(dx * dx + dy * dy);
}

class Circle {
public:
    Point c;
    double r;
    Circle(const Point& _c = Point(), double _r = 0.) : c(_c), r(_r) {}
};

istream& operator >> (istream& in, Circle& C)
{
    in >> C.c >> C.r;
    return in;
}

int CircStatus(const Circle& C1, const Circle& C2)
{
    double d = Dist(C1.c, C2.c);
    if (d > C1.r + C2.r + eps) {
        return 4;
    } else if (d > C1.r + C2.r -eps) {
        return 3;
    } else if (d > fabs(C1.r - C2.r) + eps) {
        return 2;
    } else if (d > fabs(C1.r - C2.r) - eps) {
        return 1;
    } else {
        return 0;
    }
}

class Vector {
public:
    double x, y;
    Vector(double _x = 0., double _y = 0.) : x(_x), y(_y) {}
    Vector(const Point& P) : x(P.x), y(P.y) {}
    Vector(const Point& St, const Point& End) : x(End.x - St.x), y(End.y - St.y) {}
    inline double InnerProd(const Vector& V) const
    {
        return x * V.x + y * V.y;
    }
    inline double OuterProd(const Vector& V) const
    {
        return x * V.y - y * V.x;
    }
    inline double Length() const
    {
        return sqrt((*this).InnerProd(*this));
    }
};

Vector operator+(const Vector& V1, const Vector& V2)
{
    return Vector(V1.x + V2.x, V1.y + V2.y);
}

Vector operator-(const Vector& V1, const Vector& V2)
{
    return Vector(V1.x - V2.x, V1.y - V2.y);
}

Vector operator*(double d, const Vector& V)
{
    return Vector(d * V.x, d * V.y);
}

Vector operator/(const Vector&V, double d)
{
    return Vector(V.x / d, V.y / d);
}

bool operator<(const Vector& V1, const Vector& V2)
{
    return V1.x < V2.x || (V1.x == V2.x && V1.y < V2.y);
}

ostream& operator<<(ostream& out, const Vector V)
{
    out << V.x << " " << V.y;
    return out;
}

void PrintCross(const Circle& C, const Point& St, const Point& End)
{
    Vector LineVec(St, End);
    Vector LineUnitVec = LineVec / LineVec.Length();
    Vector RefVec(St, C.c);
    double ParaDist = LineUnitVec.InnerProd(RefVec);
    double PerpDist = fabs(LineUnitVec.OuterProd(RefVec));
    double ParaDistDiff = sqrt(C.r * C.r - PerpDist * PerpDist);
    Vector Res1 = St + (ParaDist - ParaDistDiff) * LineUnitVec;
    Vector Res2 = St + (ParaDist + ParaDistDiff) * LineUnitVec;
    if (Res2 < Res1) {
        swap(Res1, Res2);
    }
    cout << Res1 << " " << Res2 << endl;
}

void PrintCrossCircles(const Circle& C1, const Circle& C2)
{
    double d = Dist(C1.c, C2.c);
    double Cos = (d * d + C1.r * C1.r - C2.r * C2.r) / (2 * d * C1.r);
    double Sin = sqrt(max(0., 1 - Cos * Cos));

    Vector ParaVec(C1.c, C2.c);
    Vector ParaUnitVec = ParaVec / ParaVec.Length();
    Vector PerpUnitVec(ParaUnitVec.y, -ParaUnitVec.x);
    
    Vector Res1 = C1.c + C1.r * Cos * ParaUnitVec + C1.r * Sin * PerpUnitVec;
    Vector Res2 = C1.c + C1.r * Cos * ParaUnitVec - C1.r * Sin * PerpUnitVec;

    if(Res2 < Res1) {
        swap(Res1, Res2);
    }
    cout << Res1 << " " << Res2 << endl;
}

Vector TiltVec(const Vector& V, double Theta)
{
    Vector Ret;
    Ret.x = V.x * cos(Theta) - V.y * sin(Theta);
    Ret.y = V.x * sin(Theta) + V.y * cos(Theta);
    return Ret;
}

void PrintTangentPoints(const Point& P, const Circle& C)
{
    double d = Dist(P, C.c);
    double l = sqrt(d * d - C.r * C.r);
    double Theta = asin(C.r / d);

    Vector RefVec(P, C.c);
    Vector RefUnitVec = RefVec / RefVec.Length();
    Vector Res1 = P + l * TiltVec(RefUnitVec, Theta);
    Vector Res2 = P + l * TiltVec(RefUnitVec, -Theta);

    if (Res2 < Res1) {
        swap(Res1, Res2);
    }
    cout << Res1 << endl << Res2 << endl;
}

void PrintCommonTangents(const Circle& C1, const Circle& C2)
{
    double d = Dist(C1.c, C2.c);
    Vector RefVec(C1.c, C2.c);
    Vector RefUnitVec = RefVec / RefVec.Length();
    vector<Vector> vRes;

    if (d > C1.r + C2.r + eps) {
        double Theta = acos((C1.r + C2.r) / d);
        vRes.push_back(C1.c + C1.r * TiltVec(RefUnitVec, Theta));
        vRes.push_back(C1.c + C1.r * TiltVec(RefUnitVec, -Theta));
    } else if (d > C1.r + C2.r -eps) {
        vRes.push_back(C1.c + C1.r * RefUnitVec);
    }

    if (d > fabs(C1.r - C2.r) + eps) {
        double Theta = acos((C1.r - C2.r) / d);
        vRes.push_back(C1.c + C1.r * TiltVec(RefUnitVec, Theta));
        vRes.push_back(C1.c + C1.r * TiltVec(RefUnitVec, -Theta));
    } else if (d > fabs(C1.r - C2.r) - eps) {
        if (C1.r > C2.r) {
            vRes.push_back(C1.c + C1.r * RefUnitVec);
        } else {
            vRes.push_back(C1.c - C1.r * RefUnitVec);
        }
    }

    sort(vRes.begin(), vRes.end());
    for (int i = 0; i < vRes.size(); ++i) {
        cout << vRes[i] <<endl;
    }
}

double AngleVecs(const Vector& V1, const Vector& V2)
{
    double Ret = atan2(V2.y, V2.x) - atan2(V1.y, V1.x);
    if (Ret > M_PI) {
        Ret -= 2 * M_PI;
    } else if (Ret < -M_PI) {
        Ret += 2 * M_PI;
    }
    return Ret;
}

double IntersectionOfCircleAndTriangle(double r, const Point& P, const Point& Q)
{
    double Ret = 0.;
    Vector VecP(P), VecQ(Q);
    Vector ParaUnitVec(P, Q);
    ParaUnitVec = ParaUnitVec / ParaUnitVec.Length();
    Vector PerpUnitVec(ParaUnitVec.y, -ParaUnitVec.x);
    double LenP = VecP.Length(), LenQ = VecQ.Length();
    double d = fabs(PerpUnitVec.InnerProd(P));

    if (LenP < r && LenQ < r) {
        Ret = VecP.OuterProd(VecQ);
    } else if (LenP < r && LenQ >= r) {       
        Vector VecX = VecP + (sqrt(r * r - d * d) - VecP.InnerProd(ParaUnitVec)) * ParaUnitVec;
        Ret += VecP.OuterProd(VecX);
        Ret += r * r * AngleVecs(VecX, VecQ);
    } else if (LenP >= r && LenQ < r) {
        Vector VecX = VecQ - (sqrt(r * r - d * d) + VecQ.InnerProd(ParaUnitVec)) * ParaUnitVec;
        Ret += r * r * AngleVecs(VecP, VecX);
        Ret += VecX.OuterProd(VecQ);
    } else if (VecP.InnerProd(ParaUnitVec) * VecQ.InnerProd(ParaUnitVec) < -eps && d < r) {
        Vector VecX = VecP + (sqrt(LenP * LenP - d * d) - sqrt(r * r - d * d)) * ParaUnitVec;
        Vector VecY = VecX + 2 * sqrt(r * r - d * d) * ParaUnitVec;
        Ret += r * r * AngleVecs(VecP, VecX);
        Ret += VecX.OuterProd(VecY);
        Ret += r * r * AngleVecs(VecY, VecQ);
    } else {
        Ret = r * r * AngleVecs(VecP, VecQ);
    }

    return Ret / 2.;
}

double IntersectionOfCircleAndPolygon(double r, const vector<Point>& vP)
{
    double Ret = 0.;
    int n = vP.size();
    for (int i = 0; i < n - 1; ++i) {
        Ret += IntersectionOfCircleAndTriangle(r, vP[i], vP[i + 1]);
    }
    Ret += IntersectionOfCircleAndTriangle(r, vP[n - 1], vP[0]);
    return Ret;
}

int main()
{
    int n;
    double r;
    cin >> n >> r;

    vector<Point> vP(n);
    for (int i = 0; i < n; ++i) {
        cin >> vP[i];
    }

    cout << fixed << setprecision(10);
    cout << IntersectionOfCircleAndPolygon(r, vP) << endl;
    
    return 0;
}