315. The Highway Belt

Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard

In the country of Berland the decision was made to build a highway belt. The king Berbinduk IX wants the highway belt to be a closed polyline and have the star-like form around the capital of Berland. This means that each half-line starting from the capital intersects the highway belt in exactly one point.

To save time and money the king decided to build the highway using only existing roads. More specifically, the highway polyline should be formed by existing roads and parts of exisiting roads.

You are the head of the First Berland National Road Building Company, and you got the contract to build the highway. Now you need to present a plan of the new highway to the king. The longer it will be the more money you will earn. So your task is to create a plan with maximal possible length of the belt highway without breaking the king's requests listed above.

The first line of the input contains the number of the existing roads N (1 ≤ N ≤ 50). The following N lines contain the description of the roads. Each description is four integer numbers x1, y1, x2, y2 not exceeding 100 by absolute value. (x1, y1) is one of the end points of the existing road and (x2, y2) is another. A road is allowed to have zero length.

The capital is situated in the origin of the coordinate system.

Write to the output the maximum possible length of the highway belt with precision of no less than 5 digits after the decimal point. If it is impossible to build a highway belt of positive length, write 0 to the output.

sample input
sample output
2 2 2 -2
-2 2 -2 -2
2 2 -2 2
-2 -2 2 -2
3 0 -1 4
-2 1 0 3 

sample input
sample output
1 1 -1 -1

Online Contester Team © 2002 - 2010. All rights reserved.