COMPASS - Broken Compass

A group of adventurers are on an expedition to reach the North Pole. The only instrument they have is a compass that points to the pole. However, the compass is broken and although its measurements are consistent, the direction it points to is some fixed but unknown angle away from true North. For example, if the error angle is 90 degrees, the compass will always point East at times when it should point North. This error angle may be zero, in which case the compass is not broken.

Input

To overcome this difficulty the group decided to take measurements at several different points and try to recover the location of the North pole from that. For simplicity, we assume that the region around the North pole is a plane in which a coordinate system is introduced. Each point is then described by a pair of real numbers (x,y), x,y ∈ [-200, 200]. One of those points (not necessarily (0,0)) is the location of the pole. The compass would always point to that location if it were not broken. Instead, it always points a fixed angle away from the true direction to the pole. In this problem we assume that the magnetic pole is the same as the geographic pole and that it is a point source.

Output

The first line of input specifies one integer number N, N < 10, the number of measurements taken. Each of the next N lines contains four space separated real numbers: the first two are the x and y coordinates of the point at which the measurement was taken, the third and fourth are (ux, uy), the direction of a unit vector indicating where the compass needle points. There should be only one line of output that should contain two real numbers separated by space: the x and y coordinates of the pole. Your output is considered correct if it is within an additive 0.01 of the correct answer. All measurements are consistent and it is always possible to determine the location of the North pole from them. None of the measurements is made on the pole.

Example

Input:
4
1.000000 0.000000 -0.000000 -1.000000
-1.000000 0.000000 0.000000 1.000000
0.000000 1.000000 1.000000 0.000000
0.000000 -1.000000 -1.000000 0.000000

Output:
0.000000 0.000000

Added by:Minilek
Date:2008-01-10
Time limit:5.970s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT 1st Team Contest 2007

hide comments
2009-09-20 13:58:27 [Trichromatic] XilinX
(ux, uy) is the direction of a unit vector indicating where the compass needle points. This means the angle between where the compass needle points and the X-axis is atan2(uy,ux).
Almost all my wrong submissions are caused by this.

Last edit: 2009-09-21 04:20:49
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.