Along which line
The epicentres of strong earthquakes are not scattered over the planet at random: they stretch along the boundaries of lithospheric plates. Find the direction along which a cloud of epicentres is most stretched, the first principal component, and what share of the points’ spread it explains.
Given n points on a plane. For a unit direction u, the spread along it is the mean square deviation of the projections of the points onto u from their mean. Find the direction u with the greatest spread and print the angle between u and the x axis, measured anticlockwise, in degrees from 0 to 180 (the directions u and −u are the same). As the second number print the share: the greatest spread divided by the sum of the spreads along x and along y.
Tests three to five are real epicentres of earthquakes of magnitude 5 and up in 2015–2025 from the USGS catalogue in three belts; the coordinates are kilometres east and north of a distant point.
Input
The first line holds n (1 ≤ n ≤ 10⁵), then n lines with integer coordinates x, y (of absolute value at most 10⁶).
Output
The angle and the share separated by a space; the angle is checked to 10⁻⁶ degrees (0 and 180 are the same), the share to 10⁻⁶. If the spread is the same in all directions, the cloud is “round” and there is no such direction, print -.
Examples
Example 1
6 100 102 104 105 108 107 111 111 115 113 118 117
39.297813375 0.995535677
Example 2
4 5 0 -5 0 0 5 0 -5
-
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
The spread along the direction u = (cos φ, sin φ) is a quadratic function of cos φ and sin φ. Through which three numbers is it expressed?
2Hint 2
It is uTSu for the 2 × 2 covariance matrix S. Where does a quadratic form on a circle have its maximum?
3The idea
Let a be the variance in x, b in y, c the covariance. The spread along φ equals a cos²φ + 2c sin φ cos φ + b sin²φ = (a + b)/2 + ((a − b)/2)·cos 2φ + c·sin 2φ. This is a sinusoid in 2φ, and its maximum is at 2φ = atan2(2c, a − b). The greatest value is (a + b)/2 plus the amplitude √(((a − b)/2)² + c²): this is the larger eigenvalue of the covariance matrix, and a + b is the sum of both. If a = b and c = 0, the amplitude is zero, and all directions are equal.
4Walkthrough
The main thing is to centre: spread is measured about the centre of mass of the cloud. To make the “round cloud” check exact, it is convenient to compute in integers the quantities n²·a = nΣx² − (Σx)², n²·b and n²·c = nΣxy − ΣxΣy: the common factor n² changes neither the angle nor the share. In Python integers do not overflow, while in Go these products reach 10²² and do not fit in int64: math/big or 128-bit arithmetic is needed. The difference a − b is also better taken exactly and only then converted to float.
On earthquakes the lines familiar from maps appear: the belt along the western edge of a continent stretches almost north to south (82.5° from the direction east, 92% of the spread along the axis), the arc of islands in the north of the Pacific almost west to east (18.7°, 98%).
4+Solution
5Complexity
O(n): five sums in one pass.
6Common mistakes
- Not centring. Second moments about the origin instead of the centre of mass. For a cloud far from zero the “principal axis” then points from the origin towards the cloud, whatever its shape. Caught by the very first example.
- atan instead of atan2. atan(2c/(a − b)) does not tell which of the two perpendicular directions is the maximum and which the minimum, and fails at a = b.
- An angle outside [0, 180). A direction without sign: −30° and 150° are one axis, and 150 must be printed.