#icpc2014autumnh. [icpc2014autumn_h]Points and Lines
[icpc2014autumn_h]Points and Lines
问题描述
有一天,你发现了一卷带有奇怪文字的古卷。
你发现这些文字实际上是表示宝藏位置的表达式。该表达式包含以下三种操作:
- 从两个点中得到一条直线。
- 从一个点和一条直线中,得到相对于给定直线对称的点。
- 从两条直线中,得到两条直线的交点。
表达式的语法如下所示:
<expression> ::= <point>
<point> ::= <point-factor> | <line> "@" <line-factor> | <line> "@" <point-factor> | <point> "@" <line-factor>
<point-factor> ::= "(" <number> "," <number> ")" | "(" <point> ")"
<line> ::= <line-factor> | <point> "@" <point-factor>
<line-factor> ::= "(" <line> ")"
<number> ::= <zero-digit> | <positive-number> | <negative-number>
<positive-number> ::= <nonzero-digit> | <positive-number> <digit>
<negative-number> ::= "-" <positive-number>
<digit> ::= <zero-digit> | <nonzero-digit>
<zero-digit> ::= "0"
<nonzero-digit> ::= "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"```
每个<point>或<point-factor>表示一个点,而每个<line>或<line-factor>表示一条直线。前者的表示形式<point-factor> $(X,Y)$ 表示平面上具有$x$坐标为$X$,$y$坐标为$Y$的点。"@"表示两个操作数之间的操作。由于每个操作通过它们的操作数类型(即点或直线)与其他操作区分开来,所有这些操作都由相同的字符"@"表示。请注意,"@"是左结合的,可以从 BNF 中看出。
您的任务是确定宝藏的位置。
* * *
### 输入
输入由多个数据集组成。每个数据集是单独的一行,其中包含表示宝藏位置的表达式。
保证每个数据集满足以下条件:
* 字符串的长度不超过$10^2$。
* 如果 "@" 的两个操作数都是点,则它们的距离大于1。
* 如果 "@" 的两个操作数都是直线,则它们永远不会平行。
* 在计算的任何时刻,点的坐标的绝对值不会超过 $10^2$。
您还可以假设最多有 $100$ 个数据集。
输入以只包含单个"#"的行结束。
### 输出
对于每个数据集,按顺序打印表达式表示的点的 $X$ 和 $Y$ 坐标。
如果输出的绝对值或相对误差不超过 $10^{-2}$,将被视为正确。
* * *
### 样例输入
```plain
((0,0)@(1,1))@((4,1)@(2,5))
((0,0)@(3,1))@((1,-3)@(2,-1))
(0,0)@(1,1)@(4,1)
(0,0)@((1,1)@(4,1))
(((0,0)@((10,20)@(((30,40))))))
((0,0)@(3,1))@((1,-3)@(2,-1))@(100,-100)@(100,100)
#```
### 样例输入输出
```plain
3.00000000 3.00000000
3.00000000 1.00000000
1.00000000 4.00000000
0.00000000 2.00000000
-10.00000000 10.00000000
-99.83681795 -91.92248853```
* * *
出处:JAG Practice Contest for ACM-ICPC Asia Regional 2014
* * *