题目描述

堡堡为您准备了一份披萨！这个披萨是一个凸多边形，每条饼边里都有芝士夹心。但这些夹心边很脆弱，导致切披萨的时候只能经过多边形的顶点，而不能从边的中间切开。不幸的是，披萨上有一片您肯定不喜欢的，巨大的圆形菠萝片。

求沿着直线切一刀之后，可以获得的最大的没有菠萝的披萨的面积。称一块披萨上没有菠萝，当且仅当菠萝没有任何部分严格位于披萨块内。也就是说，菠萝和披萨的相交面积为 $0$。

输入格式

有多个测试数据。第一行输入一个整数 $T$ 表示测试数据组数。对于每组测试数据：

第一行输入一个整数 $n$（$3 \le n \le 10^5$）表示披萨的顶点数。

第二行输入三个整数 $x_c$，$y_c$ 和 $r$（$-10^9 \le x_c,y_c \le 10^9$，$1 \le r \le 10^9$）表示菠萝的中心坐标和半径。

对于接下来的 $n$ 行，第 $i$ 行输入两个整数 $x_i$ 和 $y_i$（$-10^9 \le x_i,y_i \le 10^9$）表示第 $i$ 个顶点的坐标。顶点按逆时针顺序列出。保证任意两点不重合。但可能有三个点在同一直线上。

保证菠萝的任何部分都不会超出披萨的边界。另外保证所有数据 $n$ 之和不超过 $10^5$。

输出格式

每组测试数据输出一行一个整数，表示最大的没有菠萝的披萨的面积乘以 $2$。可以证明这个值始终是一个整数。如果无法切出没有菠萝的披萨块，输出 $0$。

3
5
1 1 1
0 0
1 0
5 0
3 3
0 5
6
2 4 1
2 0
4 0
6 3
4 6
2 6
0 3
4
3 3 1
3 0
6 3
3 6
0 3

5
24
0

提示

样例数据如下图所示。

:::align{center} :::