Hide

Problem F
Fence Fee

Languages en is
/problems/fencefee/file/statement/en/img-0001.png
Generated from OpenStreetMap, ODBL 1.0

The National Crop Protection Commission (NCPC) is dedicated to supporting local farmers by offering subsidies that are proportional to the area of their crop fields. Each farmer can have several crop fields, each uniquely shaped but geometrically defined as a polygon, bounded by fences that meet only at the corners.

In a classic display of political bureaucracy, and to incentivize well-shaped fields, the NCPC will subsidize each crop field based on the square of its area. This, to reward well-encapsulated fields. They now require a tool that calculates the sum of the squared areas of these polygons to ensure that the subsidies are distributed fairly.

Input

The first line contains an integer $F$ ($3 \leq F \leq 1000$), the number of fence line segments. The next $F$ lines contain four integers each, $x_1$, $y_1$, $x_2$, $y_2$ ($0 \leq x_1, y_1, x_2, y_2 \leq 1000$), representing a straight-line fence section.

No two fence line segments intersect. Since fencing is both expensive and tedious, you may assume that every fence line segment is necessary and serves to bound fields. All fences farmers have are connected.

In other words, the graph that consists of endpoints and fences is planar, connected, and has no bridges.

Output

Output a single line representing the sum of the squared areas of all the fields formed by the given fence sections. Your answer will be correct if it has an absolute or relative error of at most $10^{-6}$.

Explanation of sample

The picture represents sample 2. The areas of the two fields are $1$ and $0.5$, so the sum of their squares is $1 + 0.25 = 1.25$.

\includegraphics[width=0.2\textwidth ]{sample2}
Sample Input 1 Sample Output 1
5
0 0 0 1
0 1 1 1
0 0 1 0
1 0 2 0
1 1 2 0
2.25
Sample Input 2 Sample Output 2
6
0 0 0 1
0 1 1 1
0 0 1 0
1 0 2 0
1 1 2 0
1 0 1 1
1.25

Please log in to submit a solution to this problem

Log in