#P17921. Fortress

Fortress

Fortress

题目描述

堡垒的区域是平面上以原点为圆心、半径为 RR 的圆盘。圆盘内有 nn 个边平行于坐标轴的矩形,矩形之间可以重叠。

一个点被阻挡,当且仅当它严格位于至少一个矩形内部。矩形边界本身不属于该矩形的内部;但边界上的点仍可能位于其他矩形内部。

观察者位于圆盘内一个未被阻挡的点 (x,y)(x,y)。圆盘内一点 (x′,y′)(x',y') 可见,当且仅当连接它与观察者的线段上所有点(包括两个端点)都未被阻挡。求可见点集的面积。

输入格式

第一行一个整数 TT,表示测试数据组数。每组数据:

第一行两个整数 R,nR,n。

接下来 nn 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示一个矩形的左下角和右上角。

最后一行两个整数 x,yx,y,表示观察者的位置。

输出格式

每组数据输出一行一个实数,表示可见面积。

设你的输出为 aa,正确答案为 bb,当

∣a−b∣max⁡(1,b)≤10−6\frac{|a-b|}{\max(1,b)}\le10^{-6}

时视为正确。

数据范围

  • 1≤T≤1051\le T\le10^5,1≤R≤1061\le R\le10^6,0≤n≤1050\le n\le10^5。
  • 所有坐标均为整数,绝对值不超过 10610^6。
  • 每个矩形满足 x1<x2x_1<x_2、y1<y2y_1<y_2,且整个矩形严格位于圆盘内部,不接触圆周。
  • x2+y2<R2x^2+y^2<R^2,观察者不严格位于任何矩形内部,允许位于矩形边或顶点上。
  • 所有测试数据的 nn 之和不超过 10510^5。

样例

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