Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register
ACM ICPC 2018 World Finals
Language:
Ellipsoid
 Time Limit: 3000MS Memory Limit: 131072K Total Submissions: 110 Accepted: 24 Special Judge

Description

Given a set of points randomly sampled following a uniform distribution from the interior of a 3D ellipsoid to a certain density, can you recover the directions of the ellipsoid’s principal axes?

Input

The input consists of multiple lines. The first line contains only an integer N (1000 ≤ N ≤ 5000). Then come N lines, each containing three real numbers xi, yi, zi, the coordinate of a sample point in the Cartesian system.

The points are sampled from the interior of an ellipsoid the lengths of whose principal axes are a, b, c (0 < a, b, c < 1) such that a ≥ 1.2b, b ≥ 1.2c. The ellipsoid may be rotated and translated, and its center lies inside the unit sphere centered at the origin.

Output

Output as accurate as necessary three nonzero vectors indicating the directions of the ellipsoid's principal axes. The first line should contain that of the a-axis, the second line that of the b-axis, and the third line that of the c-axis. You do not have to elaborate on accuracy. For each axis you are allowed a margin of 2.5 degrees of deviation from the parameters used to define the ellipsoid.

Sample Input

Sample Output

```0.999960540723704 0.00851802271079874 0.00252196047877843
-0.00851856901599733 0.999963695122878 0.000205956596999169
0.00252011457634247 0.000227431964495135 -0.999996798643488```

Hint

When testing your solution against the sample test case, you should compare your result with the naïve orthonormal basis

`1 0 00 1 00 0 1`

Try to figure out subtle methods aimed solely at passing the test cases.

Source

[Submit]   [Go Back]   [Status]   [Discuss]