COMPASS - Broken Compass

no tags 

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.


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.


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.


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

0.000000 0.000000

hide comments
[Trichromatic] XilinX: 2009-09-20 13:58:27

(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

Added by:Minilek
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