0078. Lines

Input file name:	lines.in
Output file name:	lines.out
Time limit:	500 ms
Memory limit:	16 megabytes

You are given N lines in space.

Find such point that the sum of squares of distances from it to the given lines is minimal possible.

Input file

The first line of the input file contains one integer number N (1 ≤ N ≤ 1000). The following N lines contain 6 real numbers each: (x₁, y₁, z₁) and (x₂, y₂, z₂) – two different points lying on the corresponding line. All coordinates do not exceed 10³ by their absolute value.

Output file

Output three real numbers – coordinates of the point found. If there are several such points, output any one. Print all numbers with at least six digits after the decimal point.

Examples:

lines.in	lines.out
2 0 0 0 1 0 0 0 0 1 0 1 1	0.000000 0.000000 0.500000

Source: Petrozavodsk Winter 2003. St. Petersburg Contest II, Thursday, February 06

Discuss       Submit a solution



Printable version