The Biggest Triangle

Time limit3sMemory limit512 MB

Summary

Given up to 100 lines, find the maximum perimeter of a triangle formed by any three of them, or report that no triangle exists.

Level: Medium5 of 10
Topics: Geometry, Brute force, Math, Implementation
Solved: No attempts yet

Problem

Three infinite lines define a triangle, unless they all meet at a single point or some of them are parallel.

Given a collection of infinite lines, what is the largest possible perimeter of a triangle defined by some three of the lines?

Input

The first line of input contains a single integer n (3 ≤ n ≤ 100), the number of infinite lines.

The next n lines describe the collection of infinite lines. The ith such line contains four integers x1, y1, x2, y2 (−10 000 ≤ x1, y1, x2, y2 ≤ 10 000), where (x1, y1) ≠ (x2, y2) are two distinct points lying on the ith infinite line.

Output

Print a single real number, the perimeter of the largest triangle that can be formed from three of the infinite lines. Your answer is accepted if its absolute or relative error is within 10−5 of the correct answer.

If no triangle can be formed from the given lines, print the message "no triangle" instead.

Examples3

Example 1
Input
```
3
0 0 0 1
0 0 1 0
0 1 1 0
```
Expected output
```
3.4142135624
```
Example 2
Input
```
3
0 0 0 1
0 0 1 0
0 0 1 1
```
Expected output
```
no triangle
```

Example 3

Input

Expected output

12.0000000000