#P17921. Fortress
Fortress
Fortress
题目描述
堡垒的区域是平面上以原点为圆心、半径为 的圆盘。圆盘内有 个边平行于坐标轴的矩形,矩形之间可以重叠。
一个点被阻挡,当且仅当它严格位于至少一个矩形内部。矩形边界本身不属于该矩形的内部;但边界上的点仍可能位于其他矩形内部。
观察者位于圆盘内一个未被阻挡的点 。圆盘内一点 可见,当且仅当连接它与观察者的线段上所有点(包括两个端点)都未被阻挡。求可见点集的面积。
输入格式
第一行一个整数 ,表示测试数据组数。每组数据:
第一行两个整数 。
接下来 行,每行四个整数 ,表示一个矩形的左下角和右上角。
最后一行两个整数 ,表示观察者的位置。
输出格式
每组数据输出一行一个实数,表示可见面积。
设你的输出为 ,正确答案为 ,当
时视为正确。
数据范围
- ,,。
- 所有坐标均为整数,绝对值不超过 。
- 每个矩形满足 、,且整个矩形严格位于圆盘内部,不接触圆周。
- ,观察者不严格位于任何矩形内部,允许位于矩形边或顶点上。
- 所有测试数据的 之和不超过 。
样例
2
2 3
-1 -1 0 0
-1 -1 0 1
0 -1 1 0
1 1
26 5
-3 -23 10 21
-15 3 -5 14
-12 -18 -10 -15
-5 -6 -2 8
7 -23 10 -19
-10 0
5.598332050807308
513.142778328943998