/*
Author : Hocky Yudhiono
Rab 25 Okt 2023 02:25:01
*/
#pragma GCC optimize("no-stack-protector,O3,unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int, int> PII;
typedef pair<int, int> pii;
typedef pair<LL, LL> PLL;
typedef pair<LL, LL> pll;
typedef long double ld;
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define popf pop_front
#define pf push_front
#define popb pop_back
#define pb push_back
#define fi first
#define se second
const int INFMEM = 63;
// Do dir^1 to get reverse direction
const int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1};
const int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
const char dch[4] = {'R', 'L', 'D', 'U'};
// Do (dir + 2)%4 to get reverse direction
// const int dx[8] = {-1,0,1,0,-1,1,1,-1};
// const int dy[8] = {0,1,0,-1,1,1,-1,-1};
// const char dch[4] = {'U','R','D','L'};
const double PI = 3.141592653589793;
inline void fasterios() {
cin.tie(0)->sync_with_stdio(0);
cin.exceptions(cin.failbit);
}
#define endl '\n'
const int MOD = 1000000007;
// const int MOD = 998244353;
#ifdef _WIN32
#define getchar_unlocked getchar
#endif
#define GETCHAR getchar_unlocked
inline void fastll(LL &input_number) {
input_number = 0;
int ch = GETCHAR();
int sign = 1;
while (ch < '0' || ch > '9') {
if (ch == '-') sign = -1;
ch = GETCHAR();
}
while (ch >= '0' && ch <= '9') {
input_number = (input_number << 3) + (input_number << 1) + ch - '0';
ch = GETCHAR();
}
input_number *= sign;
}
template <class T> int sgn(T x) { return (x > 0) - (x < 0); }
template<class T>
struct Point {
typedef Point P;
T x, y;
explicit Point(T X = 0, T Y = 0) : x(X), y(Y) {}
bool operator<(P p) const { return tie(x, y) < tie(p.x, p.y); }
bool operator==(P p) const { return tie(x, y) == tie(p.x, p.y); }
P operator+(P p) const { return P(x + p.x, y + p.y); }
P operator-(P p) const { return P(x - p.x, y - p.y); }
P operator*(T d) const { return P(x * d, y * d); }
P operator/(T d) const { return P(x / d, y / d); }
T dot(P p) const { return x * p.x + y * p.y; }
T cross(P p) const { return x * p.y - y * p.x; }
T cross(P a, P b) const { return (a - *this).cross(b - *this); }
// return the orientation of (*this,a,b), 1 if ccw
int ccw(P a, P b) const { return sgn((a - *this).cross(b - *this)); }
T dist2() const { return x * x + y * y; }
double dist() const { return sqrt((double)dist2()); }
// angle to x-axis in interval [-pi, pi]
double angle() const { return atan2(y, x); }
P unit() const { return *this / dist(); } // makes dist()=1
P perp() const { return P(-y, x); } // rotates +90 degrees
P normal() const { return perp().unit(); }
// returns point rotated 'a' radians ccw around the origin
P rotate(double a) const {
return P(x * cos(a) - y * sin(a), x * sin(a) + y * cos(a));
}
friend ostream& operator<<(ostream& os, P p) {
return os << "" << p.x << " " << p.y << "";
}
};
typedef Point<double> P;
typedef double db;
template<class P>
pair<int, P> lineInter(P s1, P e1, P s2, P e2) {
auto d = (e1 - s1).cross(e2 - s2);
if (d == 0) // if parallel
return { -(s1.cross(e1, s2) == 0), P(0, 0)};
auto p = s2.cross(e1, e2), q = s2.cross(e2, s1);
return {1, (s1 * p + e1 * q) / d};
}
template<class P>
int sideOf(P s, P e, P p) { return sgn(s.cross(e, p)); }
template<class P>
int sideOf(const P& s, const P& e, const P& p, double eps) {
auto a = (e - s).cross(p - s);
double l = (e - s).dist() * eps;
return (a > l) - (a < -l);
}
typedef array<P, 2> Line;
#define sp(a) a[0], a[1]
#define ang(a) (a[1] - a[0]).angle()
int angDiff(Line a, Line b) { return sgn(ang(a) - ang(b)); }
bool cmp(Line a, Line b) {
int s = angDiff(a, b);
return (s ? s : sideOf(sp(a), b[0])) < 0;
}
vector<P> halfPlaneIntersection(vector<Line> vs) {
const double EPS = sqrt(2) * 1e-8;
sort(all(vs), cmp);
vector<Line> deq(sz(vs) + 5);
vector<P> ans(sz(vs) + 5);
deq[0] = vs[0];
int ah = 0, at = 0, n = sz(vs);
rep(i, 1, n + 1) {
if (i == n) vs.push_back(deq[ah]);
if (angDiff(vs[i], vs[i - 1]) == 0) continue;
while (ah < at && sideOf(sp(vs[i]), ans[at - 1], EPS) < 0)
at--;
while (i != n && ah < at && sideOf(sp(vs[i]), ans[ah], EPS) < 0)
ah++;
auto res = lineInter(sp(vs[i]), sp(deq[at]));
if (res.first != 1) continue;
ans[at++] = res.second, deq[at] = vs[i];
}
if (at - ah <= 2) return {};
return {ans.begin() + ah, ans.begin() + at};
}
typedef double db;
typedef pair<P, db> Circle;
const double TAU = 2 * PI;
namespace CIRUT {
const int LIM = 1000;
Circle isi[LIM + 18];
int n, p[LIM * 4 + 18], q[LIM * 4 + 18], qt, ttmp;
db ans[LIM + 18], alp[LIM * 4 + 18];
void reset(int _n) {
n = _n; qt = ttmp = 0;
rep(i, 0, (n + 1) * 4 + 2) p[i] = q[i] = alp[i] = 0;
rep(i, 0, n + 1) ans[i] = 0, isi[i] = Circle();
}
int eps(db x) {
return x < -1e-8 ? -1 : x > 1e-8;
}
int cmpor(const void *i, const void *j) {
return (ttmp = eps(alp[*(int *)i] - alp[*(int *)j])) ? ttmp : q[*(int *)j] - q[*(int *)i];
}
int judge(db d, int r0, int r1) {
if (eps(d - r0 - r1) >= 0) return -1;
if (eps(d + r1 - r0) <= 0) return 0;
if (eps(d + r0 - r1) <= 0) return 1;
return 2;
}
void inter(int a, int b, int dx, int dy, db d, db &a0, db &a1) {
db da = acos((isi[a].se * isi[a].se + d * d - isi[b].se * isi[b].se) * 0.5 / (isi[a].se * d));
db ba = atan2(dy, dx); a0 = ba - da, a1 = ba + da;
if (a0 < 0) a0 += TAU;
if (a1 < 0) a1 += TAU;
}
db calcarea(int a, db a0, db a1) {
db da = a1 - a0;
if (!eps(da)) return 0;
db x0 = isi[a].fi.x + isi[a].se * cos(a0), y0 = isi[a].fi.y + isi[a].se * sin(a0);
db x1 = isi[a].fi.x + isi[a].se * cos(a1), y1 = isi[a].fi.y + isi[a].se * sin(a1);
return isi[a].se * isi[a].se * (da - sin(da)) + (x0 * y1 - x1 * y0);
}
void calc(int X) {
int covered = 1, dx, dy;
db d; qt = 0;
for (int i = 1, tmp; i <= n; ++i)
if (X != i && (dx = isi[i].fi.x - isi[X].fi.x, dy = isi[i].fi.y - isi[X].fi.y, tmp = judge(d = sqrt(dx * dx + dy * dy), isi[X].se, isi[i].se)) > 0) {
if (tmp == 1) ++covered;
else {
inter(X, i, dx, dy, d, alp[qt + 1], alp[qt + 2]);
q[++qt] = 1, p[qt] = qt;
q[++qt] = -1, p[qt] = qt;
if (eps(alp[qt - 1] - alp[qt]) > 0) {
alp[++qt] = 0, q[qt] = 1, p[qt] = qt;
alp[++qt] = TAU, q[qt] = -1, p[qt] = qt;
}
}
}
if (!qt) {ans[covered] += isi[X].se * isi[X].se * TAU; return;}
qsort(p + 1, qt, sizeof(p[0]), cmpor);
ans[covered] += calcarea(X, 0, alp[p[1]]) + calcarea(X, alp[p[qt]], TAU);
for (int i = 1; i < qt; ++i)
covered += q[p[i]], ans[covered] += calcarea(X, alp[p[i]], alp[p[i + 1]]);
}
void solve() {
rep(i, 1, n + 1) calc(i);
rep(i, 1, n + 1) ans[i] -= ans[i + 1], ans[i] *= 0.5;
}
}
// Don't forget to read all the inputs before returning!!!
int solve() {
LL n; fastll(n);
LL rr; fastll(rr);
double r = rr;
vector <P> isi(n);
trav(cur, isi) {
LL a; fastll(a);
LL b; fastll(b);
cur.x = a;
cur.y = b;
}
if (n <= 20) {
// Solve using cirut
CIRUT::reset(n + 1);
for (int i = 1; i <= n; i++) {
CIRUT::isi[i] = {isi[i - 1], r};
}
CIRUT::solve();
printf("%.9f\n", CIRUT::ans[n]);
return 0;
}
vector <Line> halfplane;
rep(i, 0, n) {
// make a circle with radius r
auto &cur = isi[i];
auto &nx = isi[(i + 1) % n];
db dist = (cur - nx).dist() / 2;
if (fabs(dist / r) >= 1) {
cout << 0 << endl;
return 0;
}
auto alpha = acos(dist / r);
if (isnan(alpha)) {
cout << 0 << endl;
return 0;
}
//masukin 4 kotak
// Kotak kanan
{
auto vec1 = nx - cur;
auto pvec1 = vec1.perp();
vec1 = vec1.unit() * r + cur;
halfplane.pb({vec1, vec1 + pvec1});
}
// Kotak kiri
{
auto vec1 = cur - nx;
auto pvec1 = vec1.perp();
vec1 = vec1.unit() * r + nx;
halfplane.pb({vec1, vec1 + pvec1});
}
auto vec = (nx - cur);
auto center1 = cur + vec.rotate(alpha).unit() * r;
auto center2 = cur + vec.rotate(-alpha).unit() * r;
halfplane.pb({center1, center1 + (cur - nx)});
halfplane.pb({center2, center2 + (nx - cur)});
// cout << center2 << endl;
}
auto res = halfPlaneIntersection(halfplane);
double ans = 0;
rep(i, 0, sz(res)) {
ans += res[i].cross(res[(i + 1) % sz(res)]);
}
printf("%.9f\n", ans / 2);
// cout << (ans) / 2 << '\n';
return 0;
}
int main() {
LL testCases = 1, tc = 0;
fastll(testCases);
while (++tc <= testCases) {
// cout << "Case #" << tc << ": ";
solve();
}
}