#P18470. Land Trade

Land Trade

Land Trade

最近,Bobo 想从一位土地所有者手中购买一块土地,但他并不想买下整个矩形地块,而只想购买其中满足一些要求的部分。

在笛卡尔坐标系中,这块矩形土地表示为

$$L=\{(x,y):x_{\min}\le x\le x_{\max},\ y_{\min}\le y\le y_{\max}\}.$$

Bobo 的要求用一个逻辑公式描述,其语法如下:

formula := "(" formula "&" formula ")"
         | "(" formula "|" formula ")"
         | "(" formula "^" formula ")"
         | "(" "!" formula ")"
         | atomic-formula
atomic-formula := "[" decimal "," decimal "," decimal "]"

其中,&、|、^ 分别表示逻辑与、包含或、异或,! 表示逻辑非;decimal 表示有符号十进制整数。原子公式 [a,b,c] 表示不等式

ax+by+c≥0.ax+by+c\ge0.

Bobo 想买下的区域,就是矩形 LL 内所有满足给定逻辑公式的点组成的集合。为了完成交易,双方需要知道该区域的面积。请计算这个面积。

输入格式

第一行包含四个整数 xmin⁡,xmax⁡,ymin⁡,ymax⁡x_{\min},x_{\max},y_{\min},y_{\max},满足 xmin⁡<xmax⁡x_{\min}<x_{\max}、ymin⁡<ymax⁡y_{\min}<y_{\max},且这四个数的绝对值均不超过 10001000。它们描述原矩形土地。

第二行给出逻辑公式。公式包含不超过 1000010000 个字符、至多 300300 个原子公式。保证公式严格符合上面的语法,符号之间没有空格,也不省略任何括号。

每个原子公式 [a,b,c] 中的系数均为整数,满足 ∣a∣,∣b∣,∣c∣≤1000|a|,|b|,|c|\le1000 且 a2+b2≠0a^2+b^2\ne0。

输出格式

输出一个数,表示 Bobo 想购买区域的面积。答案的绝对误差或相对误差不超过 10−610^{-6} 时视为正确。

原样例 1 输入

0 1 0 1
([-1,1,0]^[-1,-1,1])

原样例 1 输出

0.5

原样例 2 输入

-5 10 -10 5
((!([1,2,-3]&[10,3,-2]))^([-2,3,1]|[5,-2,7]))

原样例 2 输出

70.451693404634582

原样例 3 输入

0 1 -1 1
([1,1,1]&[-1,-1,-1])

原样例 3 输出

0

说明与原图

原资料在第二个样例的公式中用两个反斜杠表示排版换行,它们不属于实际输入。这里已将该公式连接成真实输入的一行。

前两个样例的图形如下,填色部分表示 Bobo 想购买的区域。

第一个样例:

第一个原样例的填色区域

第二个样例:

第二个原样例的填色区域