#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] 表示不等式
Bobo 想买下的区域,就是矩形 内所有满足给定逻辑公式的点组成的集合。为了完成交易,双方需要知道该区域的面积。请计算这个面积。
输入格式
第一行包含四个整数 ,满足 、,且这四个数的绝对值均不超过 。它们描述原矩形土地。
第二行给出逻辑公式。公式包含不超过 个字符、至多 个原子公式。保证公式严格符合上面的语法,符号之间没有空格,也不省略任何括号。
每个原子公式 [a,b,c] 中的系数均为整数,满足 且 。
输出格式
输出一个数,表示 Bobo 想购买区域的面积。答案的绝对误差或相对误差不超过 时视为正确。
原样例 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 想购买的区域。
第一个样例:

第二个样例:
