This page is still under construction.

Parts of this page are still being built. What you see may change.

Points and Lines

Time limit8sMemory limit512 MB

Summary
Parse an expression of points and lines joined by @, evaluate geometric operations, and print the resulting point rounded to 8 decimals.
Level

Medium6 of 10

Topics
Implementation, Math, Geometry
Solved
No attempts yet

Problem

One day you found an old scroll covered with strange text.

The text is an expression that gives the position of a treasure. The expression is built from three operations.

  • From two points, it yields the line that passes through both points.
  • From a point and a line, it yields the point symmetric to that point with respect to the line.
  • From two lines, it yields the point where the two lines cross.

The syntax of the expression is given by the following 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"

Each <point> and <point-factor> denotes a point, and each <line> and <line-factor> denotes a line. A <point-factor> of the form (X,Y) is the point whose x coordinate is X and whose y coordinate is Y on the plane. The character @ applies an operation to its two operands. The three operations are told apart by whether each operand is a point or a line, so all of them are written with the same character @. As the grammar shows, @ is left associative.

Find the position of the treasure.

Input

The input consists of several datasets. Each dataset is one line that holds one expression denoting the position of the treasure.

Each dataset satisfies the following conditions.

  • The length of the line is at most 10210^2.
  • If both operands of an @ are points, the distance between the two points is greater than 1.
  • If both operands of an @ are lines, the two lines are not parallel.
  • At every step of the evaluation, the absolute value of each coordinate of every point is at most 10210^2.

There are at most 100 datasets. The last line of the input holds a single #, and that line is not a dataset.

Output

For each dataset, print on one line the x coordinate and the y coordinate of the point denoted by the expression, in this order, separated by a single space.

Print each coordinate rounded to 8 digits after the decimal point. When a coordinate is zero, print 0.00000000 and not -0.00000000.

Examples1

  1. Example 1

    Input
    ((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)
    #
    
    Expected output
    3.00000000 3.00000000
    3.00000000 1.00000000
    1.00000000 4.00000000
    0.00000000 2.00000000
    -10.00000000 10.00000000
    -99.83681795 -91.92248853