P14229 [ICPC 2024 Kunming I] 意大利美食
题目描述
堡堡为您准备了一份披萨！这个披萨是一个凸多边形，每条饼边里都有芝士夹心。但这些夹心边很脆弱，导致切披萨的时候只能经过多边形的顶点，而不能从边的中间切开。不幸的是，披萨上有一片您肯定不喜欢的，巨大的圆形菠萝片。
求沿着直线切一刀之后，可以获得的最大的没有菠萝的披萨的面积。称一块披萨上没有菠萝，当且仅当菠萝没有任何部分严格位于披萨块内。也就是说，菠萝和披萨的相交面积为 $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$。
说明/提示
样例数据如下图所示。
:::align{center}
:::