Have you ever wondered about the most effective row and column widths for your data in an Excel sheet? You are given $$$N$$$ rows of data, with each row $$$i$$$ containing three integers $$$X_i$$$, $$$Y_i$$$, and $$$Z_i$$$, located in columns $$$1$$$, $$$2$$$, and $$$3$$$ respectively.
For each of the $$$N$$$ rows, and each of the $$$3$$$ columns, you can set its width. This width would affect the display of every cell within that row or column. This means, a cell in a row with width $$$w_r$$$ and a column with width $$$w_c$$$ has an area of $$$w_r\times w_c$$$. Note that these row and column widths don't have to be integers.
You want to set the widths of the rows and columns such that each cell's area is no less than its corresponding integer given at the start. Find the minimum total area of the entire table that can be made possible!
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 300\,000$$$) — the number of rows.
The $$$i$$$-th of the next $$$N$$$ lines contains three integers $$$X_i$$$, $$$Y_i$$$, and $$$Z_i$$$ ($$$1\leq X_i,Y_i,Z_i\leq 10^9$$$) — the integers in columns $$$1$$$, $$$2$$$, and $$$3$$$ for row $$$i$$$.
Print a single line containing single real number representing the minimum total area of the table that can be made possible.
An answer is considered correct if the relative or absolute error of your answer doesn't exceed $$$10^{-4}$$$. Formally, let your answer be $$$a$$$ and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,b)}\leq10^{-4}$$$.
4 7 6 5 6 5 4 5 4 3 4 3 6
67.66508
One possible optimal solution is to have the widths of the rows be $$$[2.93939\ldots,2.44949\ldots,2.04124\ldots,3.15076\ldots]$$$ and the widths of the columns be $$$[2.44949\ldots,2.04124\ldots,1.90430\ldots]$$$.
