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:
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <math.h>
#include <stdbool.h>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

class Point {
    public:
    double x, y;

    Point(double x = 0, double y = 0): x(x), y(y) {}

    Point operator + (Point p) { return Point(x+p.x, y+p.y); }
    Point operator - (Point p) { return Point(x-p.x, y-p.y); }
    Point operator * (double a) { return Point(a*x, a*y); }
    Point operator / (double a) { return Point(x/a, y/a); }

    double abs() {return sqrt(norm()); }
    double norm() {return x*x + y*y; }
    Point rot(int i) {
        i %= 4;
        Point rVec;
        if ( i==0 ) return Point(x, y);
        if ( i==1 ) return Point(-y, x);
        if ( i==2 ) return Point(-x, y);
        if ( i==3 ) return Point(y, -x);
        return Point(0,0);
    }
};

typedef Point Vector;

double dot(Vector a, Vector b) {
    return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b) {
    return a.x*b.y - a.y*b.x;
}

class Circle {
    public:
    double r;
    Point c;

    Circle(double r = 0, Point c = Point()): r(r), c(c) {}
};

//ポイントpがベクトルp1-p0からみて反時計回りにいるかどうか
//CCW: 1, CW: -1, ON:0
int isCCW(Point p, Point p0, Point p1){
    Vector v01 = p1 - p0;
    Vector v02 = p - p0;

    double Cross = cross(v01, v02);
    
    int out = 2;
    if (Cross>0){out = 1;}
    else if(Cross<0){out = -1;}
    else{out = 0;}

    return out;
}

Point projection(Point p1, Point p2, Point p) {
    Vector v = p2 - p1;
    Vector u = p - p1;
    Point t = p1 + v*dot(u,v)/v.norm();
    return t;
}

double getAngleArea(Point p0, Point p1, double r);
double getMiniArea(Point p0, Point p1, double r);

int main(){
    #if 0
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    #endif

    int n, r;
    cin >> n >> r;

    vector<Point> Polygon;

    for (int i=0; i<n; i++) {
        Point p;
        cin >> p.x >> p.y;
        Polygon.push_back(p);
    }

    double area = 0;
    for (int i=0; i<n; i++) {
        Point p0, p1;
        p0 = Polygon[i];
        p1 = Polygon[(i+1)%n];
        area += getMiniArea(p0, p1, r);
    }

    cout << fixed << setprecision(11) << area << endl;

    return 0;
}

double getAngleArea(Point p0, Point p1, double r) {
    double a0 = atan2(p0.y, p0.x);
    double a1 = atan2(p1.y, p1.x);
    double angle = a1 - a0;
    if (angle <= -M_PI) { angle += 2.0 * M_PI; }
    if (angle > M_PI) { angle -= 2.0 * M_PI; }
    return angle * r * r / 2.0;;
}

double getMiniArea(Point p0, Point p1, double r) {
    double d0, d1;
    d0 = p0.abs();
    d1 = p1.abs();

    Point O;

    if ( isCCW(O, p0, p1) == 0 ) {
        return 0.0;
    }

    if ( d0 <= r && d1 <= r ) {
        return cross(p0, p1) / 2.0;
    }
    else if ( d0 <= r && d1 > r ) {
        Vector eVec = p1 - p0;
        eVec = eVec / (p1 - p0).abs();
        Point proj = projection(p0, p1, O);
        double d = proj.abs();
        Point crossPoint = proj + eVec * sqrt( r*r - d*d );

        return cross(p0, crossPoint) / 2.0 + getAngleArea(crossPoint, p1, r);
    }
    else if ( d0 > r && d1 <= r ) {
        Vector eVec = p1 - p0;
        eVec = eVec / (p1 - p0).abs();
        Point proj = projection(p0, p1, O);
        double d = proj.abs();
        Point crossPoint = proj - eVec * sqrt( r*r - d*d );

        return getAngleArea(p0, crossPoint, r) + cross(crossPoint, p1) / 2.0;
    }
    else {
        Vector eVec = p1 - p0;
        eVec = eVec / (p1 - p0).abs();
        Point proj = projection(p0, p1, O);
        double d = proj.abs();

        if ( d >= r || ( isCCW(p0, O, proj) == isCCW(p1, O, proj) ) ) { 
            return getAngleArea(p0, p1, r);
        }
        else {
            Point cross0, cross1;
            cross0 = proj - eVec * sqrt( r*r - d*d );
            cross1 = proj + eVec * sqrt( r*r - d*d );
            return getAngleArea(p0, cross0, r) + cross(cross0, cross1) / 2.0 + getAngleArea(cross1, p1, r);
        }
    }
}