Hide

Problem H
Goofy Geometry

Latkas Coolacek doesn’t really like doing his mathematics homework, he prefers partying with his algorithm buddies and finding shortest paths in the city. Unfortunately, his teachers aren’t as happy with Latkas ignoring school. Thus, they have given him the worst assignment there is; boring, mindless geometry calculations!

The task given to Latkas is:

Consider a point $P$ in the 2D-plane such that the distance between $(0, 0)$ and $P$ is greater than 1. The unit circle (the circle with radius 1 and centre in $(0, 0)$) has exactly two tangent lines (lines touching the circle at a single point, and is perpendicular to the radius to that point) which pass through $P$. We then define the tangential coordinates of $P$. Write the two lines on the form $a_ ix + b_ iy = c_ i$ for $i = 1, 2$. The tangential coordinates of $P$ is then the 6-tuple $(a_1, b_1, c_1, a_2, b_2, c_2)$ (or some non-zero scaling thereof). Given $N$ points in the plane, calculate the tangential coordinates of them all.

\includegraphics[width=360px]{sample.png}

Figure 1: Illustration of sample 1

Since nobody should have to suffer through an assignment this sadistic, you offered to write a program which makes Latkas’ homework automatically. In exchange, since Latkas is such a good friend, he will make you 20% cooler.

Input

The first line of input consists of a single integer $1 \le N \le 1\, 000$, the number of points.

Then follow $N$ lines of two real numbers $|X_ i| \le 10^4, |Y_ i| \le 10^4$. These are the coordinates of the $N$ points.

Output

Output should consist of $N$ lines - the tangential coordinates of every point, in the order given by the input.

The coordinates must be formatted “($a_1$,$b_1$,$c_1$,$a_2$,$b_2$,$c_2$)”, where $a_1, b_1, c_1, a_2, b_2, c_2$ are real numbers, without any spaces.

Output will be considered correct if all the coordinates are within a relative or absolute error of $10^{-4}$.

Sample Input 1 Sample Output 1
4
4 3
-4 3
4 -3
-4 -3
(-2.096163282,4.427877538,4.898979486,-3.663836718,3.252122462,-4.898979486)
(-3.663836718,-3.252122462,4.898979486,-2.096163282,-4.427877538,-4.898979486)
(3.663836718,3.252122462,4.898979486,2.096163282,4.427877538,-4.898979486)
(2.096163282,-4.427877538,4.898979486,3.663836718,-3.252122462,-4.898979486)

Please log in to submit a solution to this problem

Log in