Hide

Problem G
Triangle Ornaments

/problems/triangleornaments/file/statement/en/img-0001.png
A company makes triangle-shaped ornaments for the upcoming holidays. Each ornament is tied at one of its corners to a rod using a string of unknown length. Multiple of these ornaments may be attached to the same rod. These ornaments should be able to swing (rotate around the axis formed by the string) without interfering with each other.

Write a program that computes the minimum required length for the rod, given a list of triangles!

Input

The input consists of a single test case. The first line contains one integer $N$ ($0 < N \le 100$), denoting the number of triangles. The next $N$ lines each contain three integers $A, B, C$ denoting the lengths of the three sides of each triangle. The triangle will hang from the corner between sides $A$ and $B$. You are guaranteed that $A, B, C$ form a triangle that has an area that is strictly greater than zero.

Output

Output the required length $L$ such that all triangles can be hung from the rod, no matter how long or short each triangle’s string is. No triangle should swing beyond the rod’s ends. You may ignore the thickness of each ornament, the width of the string and you may assume that the string is attached exactly to the triangle’s end point.

Your answer should be accurate to within an absolute or relative error of $10^{-4}$.

Sample Input 1 Sample Output 1
2
3 3 3
4 4 5
8.0
Sample Input 2 Sample Output 2
2
3 3 3
4 5 4
6.843530573929037
Sample Input 3 Sample Output 3
3
7 20 14
7 14 20
14 20 7
20.721166413503266

Please log in to submit a solution to this problem

Log in