← 返回题目列表

AtCoder · icpc2014autumn_h

H. 点和线

中文机器翻译题面 查看原题

问题陈述

有一天,你发现了一张古老的卷轴,上面写着奇怪的文字。

你透露该文本实际上是表示位置的表达式 宝藏。 该表达式由以下三个操作组成:

  • 从两个点生成一条线,这些点位于其上。
  • 从点和线生成一个相对于线与给定点对称的点。
  • 从两条线中产生一个点,该点是线的交点。

表达式的语法由以下 BNF 表示:

<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)$ 的前一个概念表示 $2$ 维平面上的一个点,该点的 $x$ 坐标为 $X$,$y$ 坐标为 $Y$。 “@”表示对两个操作数进行运算。 由于每个操作都可以通过其操作数的类型(即点或线)与其他操作区分开来, 所有这些操作都由相同的字符“@”表示。 请注意,“@”是左结合的,从 BNF 中可以看出。

你的任务是确定宝藏的放置位置。


输入

输入由多个数据集组成。 每个数据集都是一行 包含表示宝藏位置的表达式。

保证每个数据集满足以下条件:

  • 字符串的长度永远不会超过 $10^2$。
  • 如果“@”的两个操作数都是点,则它们的距离大于$1$。
  • 如果“@”的两个操作数都是线,则它们永远不会平行。
  • 在任何评估点,点坐标的绝对值都不会超过 $10^2$。

您还可以假设最多有 $100$ 数据集。

输入以仅包含单个“#”的行结束。

输出

对于每个数据集,打印该点的 $X$ 和 $Y$ 坐标,表示为 表达式,按此顺序。

如果输出的绝对或相对误差最多为 $10^{-2}$,则输出将被视为正确。


示例输入

((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)
#

样本输入的输出

3.00000000 3.00000000
3.00000000 1.00000000
1.00000000 4.00000000
0.00000000 2.00000000
-10.00000000 10.00000000
-99.83681795 -91.92248853