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 <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

#include <iostream>
#include <complex>
#include <string>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>

#include <functional>
#include <cassert>

typedef long long ll;
using namespace std;

#define debug(x) cerr << __LINE__ << " : " << #x << " = " << (x) << endl;

#define mod 1000000007 //1e9+7(prime number)
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define SIZE 100010

typedef double P_type; //座標(integer or real)
typedef double G_real; //実数の戻り値(float or double or long double)
typedef complex<P_type> P;
const G_real P_eps = 1e-8; //整数の時はゼロ

namespace std{
  template<class T> bool operator<(const complex<T> &a, const complex<T> &b){
    return abs(a.real() - b.real()) < P_eps ? a.imag() + P_eps < b.imag() : a.real() + P_eps < b.real();
  }
};

P rotate(P p, double theta){
  return p * P(cos(theta), sin(theta));
}

//内積
P_type dot(P a, P b) {
  return (a * conj(b)).real();
}

//外積
P_type cross(P a, P b) {
  return (conj(a) * b).imag();
}

//反時計回り
int ccw(P a, P b, P c){
  if(cross(b-a, c-a) > P_eps) return 1; //COUNTER_CLOCKWISE(center:a)
  if(cross(b-a, c-a) < -P_eps) return -1; //CLOCKWISE(center:a)
  if(dot(b-a, c-a) < -P_eps) return -2; //c -> a -> b
  if(dot(a-b, c-b) < -P_eps) return 2; //a -> b -> c
  return 0; //a -> c -> b
}

/* 線分abと点cの距離 */
G_real distanceSP(P a, P b, P c) {
  if ( dot(b-a, c-a) < P_eps ) return abs(c-a);
  if ( dot(a-b, c-b) < P_eps ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}

/* 直線abと点cの距離 */
G_real distanceLP(P a, P b, P c) {
  return abs(cross(b-a, c-a)) / abs(b-a);
}

/* 円の点包含判定 */
bool isContainedCP(P c, P_type r, P p){
  //return abs(c-p) < r - P_eps; //円周上を含まない
  return abs(c-p) < r + P_eps; //円周上を含む
}

/* 直線交差判定 */
bool isIntersectedLL(P a1, P a2, P b1, P b2){
  return abs(cross(a1-a2, b1-b2)) > P_eps;
}

/* 線分交差判定 */
bool isIntersectedSS(P a1, P a2, P b1, P b2){
  
  //線分a と 直線b
  int a = ccw(b1, b2, a1);
  int b = ccw(b1, b2, a2);
  
  //線分b と 直線a
  int c = ccw(a1, a2, b1);
  int d = ccw(a1, a2, b2);
  
  return a * b <= 0 && c * d <= 0; // T字を除く時は (** < 0)
}

/* 直線線分交差判定 */
bool isIntersectedLS(P a1, P a2, P b1, P b2){  
  int a = ccw(a1, a2, b1);
  int b = ccw(a1, a2, b2);
  
  // 直線上のとき a or b = 0 or -2 or 2
  return (a % 2) * (b % 2) <= 0; // T字を除く時は (** < 0)
}

/* 円交差判定 */
bool isIntersectedCC(P c1, G_real r1, P c2, P_type r2){
  G_real dist = abs(c1 - c2);
  
  return abs(r1 - r2) < dist + P_eps && dist - P_eps < r1 + r2; //外接内接を含む
  //return abs(r1 - r2) < dist - P_eps && dist + P_eps < r1 + r2; //外接内接を除く
}

/* 円直線交差判定 */
bool isIntersectedCL(P c, G_real r, P a1, P a2){
  return distanceLP(a1, a2, c) < r + P_eps; //接する場合を含まない場合 - P_eps
}

/* 円線分交差判定 */
bool isIntersectedCS(P c, P_type r, P a1, P a2){
  return (!isContainedCP(c, r, a1) || !isContainedCP(c, r, a2)) &&
    distanceLP(a1, a2, c) < r + P_eps; //接する場合を含まない場合 - P_eps
}

/* 直線/線分交点 */
P getCrosspointLL(P a1, P a2, P b1, P b2) {
  //assert(isIntersectedLL(a1, a2, b1, b2));
  P a = a2 - a1;
  P b = b2 - b1;
  return a1 + a * cross(b, b1 - a1) / cross(b, a);
}

P getCrosspointSS(P a1, P a2, P b1, P b2){
  //assert(isIntersectedSS(a1, a2, b1, b2));
  return getCrosspointLL(a1, a2, b1, b2);
}

/* 円交点 */
pair<P,P> getCrosspointCC(P c1, P_type r1, P c2, P_type r2){
  //assert(isIntersectedCC(c1, r1, c2, r2));
  
  P_type dist = abs(c1 - c2);
  P_type a = acos((r1*r1 + dist*dist - r2*r2) / (2 * r1 * dist));
  return {c1 + polar(r1, arg(c2 - c1) + a), c1 + polar(r1, arg(c2 - c1) - a)};
}

/* 円線分交点 */
vector<P> getCrosspointCL(P c, P_type r, P a1, P a2){
  if(!isIntersectedCL(c, r, a1, a2)) return {};
  
  P base1 = a2 - a1;
  P proj = a1 + base1 * dot(c - a1, base1) / norm(base1); //射影
  P e = (a2 - a1) / abs(a2 - a1);
  P base2 = sqrt(r*r - norm(proj - c));
  return {proj - e*base2, proj + e*base2};
}

vector<P> getCrosspointCS(P c, P_type r, P a1, P a2){
  if(!isIntersectedCL(c, r, a1, a2)) return {};

  vector<P> res;
  for(P p : getCrosspointCL(c, r, a1, a2))
    if(dot(a1-p, a2-p) <= P_eps) res.push_back(p);
  return res;
}

/* 多角形-点包含 */
bool iscontainedPolyP(vector<P> &g, P p){
  int n = g.size();
  bool f = false;
  for(int i=0;i<n;i++){
    P a = g[i] - p, b = g[(i+1)%n] - p;
    if(abs(cross(a,b)) < P_eps && dot(a,b) < P_eps) return true; //辺上
    if(a.imag() > b.imag()) swap(a,b);
    if(a.imag() < P_eps && P_eps < b.imag() && cross(a,b) > P_eps) f = !f;
  }
  return f; //内部 or 外部
}

/* 射影(直線abとpからの垂線との交点) */
P getProject(P a, P b, P p){
  P base = b - a;
  return a + base * dot(p - a, base) / norm(base);
}

/* 反射(直線abを対称軸としたpの線対称の位置) */
P getReflection(P a, P b, P p){
  return p + (getProject(a, b, p) - p) * (P_type)2.0;
}


/* 多角形面積 */
G_real getAreaPoly(vector<P> &g){
  P_type res = 0;
  for(int i=0;i<g.size();i++)
    res += cross(g[i], g[(i+1)%g.size()]);
  return abs(res/2.0);
}

G_real getAreaCS(P c, P_type r, P a1, P a2){
  auto getSubArea = [&](P p1, P p2){
    if(isContainedCP(c, r, p1) && isContainedCP(c, r, p2))
      return cross(p1-c, p2-c) / 2.0;
    return r*r*arg(conj(p1-c)*(p2-c)) / 2.0;
  };

  if(min({abs(a1 - a2), abs(c - a1), abs(c - a2), r}) <= P_eps) return 0;

  G_real res = 0; 
  vector<P> vec = {a1};
  for(auto p : getCrosspointCS(c, r, a1, a2)) vec.push_back(p);
  vec.push_back(a2);
  
  for(int i=0;i+1<vec.size();i++)
    res += getSubArea(vec[i], vec[i+1]);

  return res;
}

G_real getAreaPolyC(vector<P> &g, P c, P_type r){
  G_real res = 0;
  for(int i=0;i<g.size();i++)
    res += getAreaCS(c, r, g[i], g[(i+1)%g.size()]);
  return res;
}


int main(){
  int n, r;

  vector<P> vec;
  cin >> n >> r;

  
  for(int i=0;i<n;i++){
    int x, y;
    cin >> x >> y;
    vec.push_back(P(x, y));
  }

  printf("%.10lf\n", getAreaPolyC(vec, P(0,0), r));
  
  return 0;
}