Migrated from Lutece 3043 此曲一响，________

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

你电学生有很多摸鱼好手。有时候有人打开了抖音而忘记关声音，传出了一曲鬼畜音乐，运气差一些老师都能听到，全班都炸了。

想象一下现在老师在品C教室里讲课，一群学生围着老师坐，形成了一个多边形，突然在某个位置传来了一曲鬼畜声音，老师和声音源都有可能在这群学生中，也都有可能不在。对于这群学生里的每个人，如果这个人坐得离老师足够近，他就不会受到影响，反之这个人会蚌埠住笑出声。

具体来说，对于一个给定的 $k$ ，对于这个多边形（不一定是凸多边形）里的每个点，记 $d_1$ 表示它到老师所在位置的距离， $d_2$ 表示它到声音源的距离，如果 $d_2\le kd_1$ ，那么在这个点处的学生会笑出声，否则不会受影响。

现在给定这个多边形，参数 $k$ ，老师的位置和声音源的位置，请问有多少区域的学生会笑出声。有多组询问，所以还请尽快解决所有问题，不然老师要扣全班的平时分了。

Input

多组询问，第一行一个整数 $T$ 表示询问次数。

对于每组询问，第一行有一个整数 $n$ 和一个四位小数 $k$ ，表示这个多边形的点数和参数 $k$ 。

接下来有 $n$ 行，第 $i$ 行有两个整数 $x_i$ 和 $y_i$ ，表示多边形的第 $i$ 个点的坐标。多边形坐标按逆时针顺序或顺时针顺序给出。

接下来又有两行，第 $i$ 行有两个整数 $x'_i$ 和 $y'_i$ ，第一行的两个数表示老师的位置坐标，第二行的两个数表示声音源的位置坐标。保证两者不重合。

Output

对于每组询问输出一行一个数，表示会笑出声的学生区域面积。

请使用科学计数法的方式输出，保留七位有效数字（即 printf("%e\n", ans)）。

Samples

4
4 0.5000
-1 -1
1 -1
1 1
-1 1
0 0
-1 0
5 0.5000
-4 -2
0 -2
-2 0
0 2
-4 2
4 0
1 0
6 0.5000
-2 2
-2 -2
-1 2
-1 -2
-1 -2
-10 -10
4 0
1 0
3 0.5000
0 10
0 200
-10 0
0 -10
0 10

2.729710e-01
2.283185e+00
1.429399e+00
2.038916e+02

Constraints

输入保证 $1\le T\le 100$ ，$1\le n\le 500$，所有坐标的绝对值不大于 $10^3$ ，$0.2\le k\le 0.8$ 。

Resources

2023 UESTC ICPC Training for Geometry