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:
/*
* 多边形和圆面积并
* Complier: G++
* Create Time: 8:26 2015/10/1 星期四
*/
#include <algorithm>
#include <iostream>
#include <math.h>
#include <stdio.h>
#include <string.h>
using namespace std;

const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
const int maxn = 1005;
double R, k;
int n, m;
typedef struct point vec; //向量vec
struct point { //点的基本数据结构
    double x, y;
    point(double _x = 0.0, double _y = 0.0)
        : x(_x)
        , y(_y)
    {
    }
    double sqrx() //向量的模
    {
        return sqrt(x * x + y * y);
    }
    point operator*(const point& i_T) const
    {
        return point(x * i_T.x, y * i_T.y);
    }
    point operator*(double u) const
    {
        return point(x * u, y * u);
    }
    bool operator==(const point& i_T) const
    {
        return x == i_T.x && y == i_T.y;
    }
    point operator/(double u) const
    {
        return point(x / u, y / u);
    }
    point operator+(const point& i_T)
    {
        return point(x + i_T.x, y + i_T.y);
    }
    point operator-(const point& i_T)
    {
        return point(x - i_T.x, y - i_T.y);
    }
    friend bool operator<(point a, point b)
    {
        return a.y == b.y ? a.x < b.x : a.y < b.y;
    }
    friend ostream& operator<<(ostream& out, point& a)
    {
        //cout << a.x << ' ' << a.y;
        printf("%.8f %.8f", a.x, a.y);
        return out;
    }
    friend istream& operator>>(istream& in, point& a)
    {
        in >> a.x >> a.y;
        return in;
    }
};
struct cirles {
    point o;
    double r;
    cirles(point _o = point(), double _r = 0.0)
        : r(_r)
        , o(_o)
    {
    }
    point Point(double t) //圆上任意一点
    {
        return point(o.x + r * cos(t), o.y + r * sin(t));
    }
    friend istream& operator>>(istream& in, cirles& a)
    {
        in >> a.o >> a.r;
        return in;
    }
    friend ostream& operator<<(ostream& out, cirles& a)
    {
        out << a.o << ' ' << a.r;
        return out;
    }
};
typedef struct Line Segment; //线段Segment
struct Line { //直线
    point a, b;
    Line(point _a = point(), point _b = point())
        : a(_a)
        , b(_b)
    {
    }
    friend istream& operator>>(istream& in, Line& a)
    {
        cin >> a.a >> a.b;
        return in;
    }
    friend ostream& operator<<(ostream& out, Line& a)
    {
        out << a.a << ' ' << a.b;
        return out;
    }
};
point area[maxn];

int dcmp(double x) //判断和0的关系
{
    return (x > eps) - (x < -eps);
}

double chaji(vec A, vec B) //求向量叉积
{
    return A.x * B.y - A.y * B.x; // 正为A->B左旋
}

double changdu(vec a) //向量长度
{
    return sqrt(a.x * a.x + a.y * a.y);
}

point zhixian_zhixian_jiaodian(Line l1, Line l2) //两直线交点
{
    double t = ((l1.a.x - l2.a.x) * (l2.a.y - l2.b.y) - (l1.a.y - l2.a.y) * (l2.a.x - l2.b.x)) / ((l1.a.x - l1.b.x) * (l2.a.y - l2.b.y) - (l1.a.y - l1.b.y) * (l2.a.x - l2.b.x));
    return l1.a + (l1.b - l1.a) * t;
}

void zhixian_yuan_jiaodian(cirles c, Line l, point& p1, point& p2) //直线与圆相交的交点
{
    point p = c.o;
    double t;
    p.x += l.a.y -l.b.y;
    p.y += l.b.x - l.a.x;
    p = zhixian_zhixian_jiaodian(Line(p, c.o), l);
    t = sqrt(c.r * c.r - changdu(p - c.o) * changdu(p - c.o)) / changdu(l.a - l.b);
    p1 = p + (l.b- l.a) * t;
    p2 = p- (l.b - l.a) * t;
}

point dian_dao_xianduan(point p, Segment l) //点到线段的最近距离
{
    point t = p;
    t.x += l.a.y - l.b.y;
    t.y += l.b.x - l.a.x;
    if (chaji(l.a - p, t - p) * chaji(l.b - p, t - p ) > eps)
        return changdu(p - l.a) < changdu(p - l.b) ? l.a : l.b;
    return zhixian_zhixian_jiaodian(Line(p, t), l);
}

double distp(Line l) //长度的平方
{
    return (l.a.x - l.b.x) * (l.a.x - l.b.x) + (l.a.y - l.b.y) * (l.a.y - l.b.y);
}
double yuanxin_dian_sanjiao(Line l, cirles c) //求圆心与两点所成三角形有向面积
{
    double sign = 1.0;
    l.a = l.a - c.o;
    l.b = l.b - c.o;
    c.o = point(0.0, 0.0);
    if (fabs(chaji(l.a - c.o, l.b - c.o)) < eps)
        return 0.0;
    if (distp(Line(l.a, c.o)) > distp(Line(l.b, c.o))) {
        swap(l.a, l.b);
        sign = -1.0;
    }
    if (distp(Line(l.a, c.o)) < c.r * c.r + eps) { //a在圆内
        if (distp(Line(l.b, c.o)) < c.r * c.r + eps) //b也在圆内,返回叉积/2
            return chaji(l.a - c.o, l.b - c.o) / 2.0 * sign;
        point p1, p2;
        zhixian_yuan_jiaodian(c,l, p1, p2); //oa和ob与圆的交点
        if (changdu(p1 - l.b) > changdu(p2 - l.b))
            swap(p1, p2);
        double ret1 = fabs(chaji(l.a - c.o, p1 - c.o));
        double ret2 = acos((p1.x * l.b.x + p1.y * l.b.y) / p1.sqrx() / l.b.sqrx()) * c.r * c.r;
        double ret = (ret1 + ret2) / 2.0;
        if (chaji(l.a - c.o, l.b - c.o) < eps && sign > 0.0 || chaji(l.a - c.o, l.b - c.o) > eps && sign < 0.0)
            ret = -ret;
        return ret;
    }
    point ins = dian_dao_xianduan(c.o, l);
    if (distp(Line(c.o, ins)) > c.r * c.r - eps) {
        double ret = acos((l.a.x * l.b.x + l.a.y * l.b.y) / l.a.sqrx() / l.b.sqrx()) * c.r * c.r / 2.0;
        if (chaji(l.a - c.o, l.b - c.o) < eps && sign > 0.0 || chaji(l.a - c.o, l.b - c.o) > eps && sign < 0.0)
            ret = -ret;
        return ret;
    }
    point p1, p2;
    zhixian_yuan_jiaodian(c, l, p1, p2);
    double cm = c.r / (changdu(c.o - l.a) - c.r);
    point m = point((c.o.x + cm * l.a.x) / (1 + cm), (c.o.y + cm * l.a.y) / (1 + cm));
    double cn = c.r / (changdu(c.o - l.b) - c.r);
    point n = point((c.o.x + cn * l.b.x) / (1 + cn), (c.o.y + cn * l.b.y) / (1 + cn));
    double ret1 = acos((m.x * n.x + m.y * n.y) / m.sqrx() / n.sqrx()) * c.r * c.r;
    double ret2 = acos((p1.x * p2.x + p1.y * p2.y) / p1.sqrx() / p2.sqrx()) * c.r * c.r - fabs(chaji(p1 - c.o, p2 - c.o));
    double ret = (ret1 - ret2) / 2.0;
    if (chaji(l.a - c.o, l.b - c.o) < eps && sign > 0.0 || chaji(l.a - c.o, l.b - c.o) > eps && sign < 0.0)
        ret = -ret;
    return ret;
}
point a[1000];
int main()
{
    cirles c;
    int n;
    scanf("%d%lf", &n, &c.r);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    a[0] = a[n];
    double sum = 0;
    for (int i = 0; i < n; i++) {
        sum += yuanxin_dian_sanjiao(Line(a[i], a[i + 1]), c);
    }
    printf("%.10f\n", sum);
}