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 <bits/stdc++.h>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
//typedef pair<ll, ll> P;
//const double INF = 1e10;
//const ll INF = LONG_LONG_MAX / 100;
//const ll INF = (1ll << 31) - 1;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

//bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;


void print_line(vector<string> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}

using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }
const double eps = 1e-10;
const double inf = 1e+10;
const double pi = acos(-1.0);
int sgn(double a) { return a < -eps ? -1 : a > eps; }
using P = complex<double>;
namespace std {
    istream& operator>>(istream& i, P& p) { double x, y; i >> x >> y; p = P(x, y); return i; }
    ostream& operator<<(ostream& o, const P& p) { o << real(p) << ' ' << imag(p); return o; }
    bool operator<(const P& p, const P& q) { return sgn(real(p) - real(q)) ? sgn(real(p) - real(q)) < 0 : sgn(imag(p) - imag(q)) < 0; }
    bool operator>(const P& p, const P& q) { return q < p; }
    bool operator<=(const P& p, const P& q) { return !(p > q); }
    bool operator>=(const P& p, const P& q) { return !(p < q); }
}
bool eq(const P& p, const P& q) { return !(p < q) and !(p > q); }
double dot(const P& p, const P& q) { return real(conj(p) * q); }
double cross(const P& p, const P& q) { return imag(conj(p) * q); }

P proj(P p1, P p2, P p) {
    p2 -= p1, p -= p1;
    return p1 + dot(p2, p) / norm(p2) * p2;
}

int ccw(P p0, P p1, P p2) {
    p1 -= p0, p2 -= p0;                         //             (1)
    if (sgn(cross(p1, p2)) > 0) return 1;       //
    if (sgn(cross(p1, p2)) < 0) return -1;      // (-2)---p0---(0)---p1---(2)
    if (sgn(dot(p1, p2) < 0)) return -2;        //
    if (sgn(norm(p1) - norm(p2)) < 0) return 2; //             (-1)
    return 0;
}

bool intLP(const P& p1, const P& p2, const P& p) {
    return !(ccw(p1, p2, p) & 1);
}

bool intSP(const P& p1, const P& p2, const P& p) {
    return !ccw(p1, p2, p);
}

double distLP(const P& p1, const P& p2, const P& p) {
    if (intLP(p1, p2, p)) return 0.0;
    return abs(p - proj(p1, p2, p));
}

double distSP(const P& p1, const P& p2, const P& p) {
    P q = proj(p1, p2, p);
    if (intSP(p1, p2, q)) return distLP(p1, p2, p);
    return min(abs(p1 - p), abs(p2 - p));
}

V<P> intPCL(const P& o, double r, const P& p1, const P& p2) {
    P p = proj(p1, p2, o), q = sqrt(max(r * r - norm(p - o), 0.0)) / abs(p1 - p2) * (p2 - p1);
    return V<P>({p + q, p - q});
}

double areaTC(const P& p1, const P& p2, double r) {
    if (ccw(P(0.0, 0.0), p1, p2) & 1 == 0) return 0.0;
    if (sgn(norm(p1) - r * r) <= 0 and sgn(norm(p2) - r * r) <= 0) {
        return 0.5 * cross(p1, p2);
    } else if (sgn(norm(p1) - r * r) <= 0) {
        V<P> ps = intPCL(P(0.0, 0.0), r, p1, p2);
        P p = sgn(abs(ps[0] - p2) - abs(ps[1] - p2)) < 0 ? ps[0] : ps[1];
        // P p = ccw(p1, p2, ps[0]) == 0 ? ps[0] : ps[1];
        return 0.5 * (cross(p1, p) + r * r * arg(p2 / p));
    } else if (sgn(norm(p2) - r * r) <= 0) {
        V<P> ps = intPCL(P(0.0, 0.0), r, p1, p2);
        P p = sgn(abs(ps[0] - p1) - abs(ps[1] - p1)) < 0 ? ps[0] : ps[1];
        // P p = ccw(p1, p2, ps[0]) == 0 ? ps[0] : ps[1];
        return 0.5 * (r * r * arg(p / p1) + cross(p, p2));
    } else if (sgn(distSP(p1, p2, P(0.0, 0.0)) - r) >= 0) {
        return 0.5 * r * r * arg(p2 / p1);
    } else {
        V<P> ps = intPCL(P(0.0, 0.0), r, p1, p2);
        if (ccw(p1, ps[0], ps[1]) == 0) swap(ps[0], ps[1]);
        return 0.5 * (r * r * (arg(ps[0] / p1) + arg(p2 / ps[1])) + cross(ps[0], ps[1]));
    }
}

int main() {
    cin.tie(NULL); ios::sync_with_stdio(false);
    int n; double r; cin >> n >> r;
    V<P> g(n); for (int i = 0; i < n; i++) cin >> g[i];
    double res = 0.0;
    for (int i = 0; i < n; i++) res += areaTC(g[i], g[(i + 1) % n], r);
    cout << fixed << setprecision(12) << res << '\n';
}