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>
using namespace std;
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';
}