Problem Description

Translated from PA 2018 Round 3 Magiczne wieże.

In a kingdom, there are $n$ wizards. Each wizard has two magic towers. A wizard can teleport freely between their two towers.

For some reason, the residents of the kingdom only want to live in areas surrounded by wizards. Specifically, if a resident moves from their home in any direction, they will get closer to at least one wizard (at either of that wizard's towers), then their home is considered safe.

If we connect all safe homes in order, they form a safe region. Please find the area of this region.

Input Format

The first line contains an integer $n$, which represents the number of wizards.

The next $n$ lines each contain $4$ integers $ax_i, ay_i, bx_i, by_i$, describing the two magic towers $a, b$ owned by the $i$-th wizard.

It is guaranteed that no two towers are at the same position.

Output Format

Output the area of the safe region. In particular, if there are no safe points, the area of the region is $0$.

Your output must have relative error at most $10^{-8}$ compared with the standard answer.

4
0 0 0 -1
-1 5 -2 2
4 0 4 1
2 2 6 6

4.8000000000

Hint

Explanation for Sample 1

As shown in the figure, the black line segments are the two towers of a wizard, and the gray area is the safe region.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $3 \leq n \leq 100$, $-500 \leq ax_i, ay_i, bx_i, by_i \leq 500$.

There are $10$ subtasks. Among them, for each of the following conditions, there is at least one subtask that satisfies it (each line is one condition):

• $n \leq 10$, $-30 \leq ax_i, ay_i, bx_i, by_i \leq 30$.
• $n \leq 10$.
• $-30 \leq ax_i, ay_i, bx_i, by_i \leq 30$.

Translated by ChatGPT 5