Under construction

Still being built. Things may change

Magic Towers

Time limit1sMemory limit1024 MB

Summary
Given n mages with two towers each, find the area of points where every movement direction brings you closer to both towers of some mage.
Level

Hard8 of 10

Topics
Geometry, Math
Solved
No attempts yet

Problem

In Bitocja there live n mages, and each of them owns two towers. Each mage can teleport between their two towers, so the other Bitocjans (ordinary citizens) cannot tell which of the two towers a given mage is in.

For reasons that are more or less rational, Bitocjans like to surround themselves with mages. We say a Bitocjan feels safe if they stand at a point such that, no matter which direction they move in, they get closer to one of the mages (regardless of which towers the mages currently occupy). Bitocjans prefer to build their houses only at points where they feel safe. All such points form the safe region.

Find the area of the safe region. It may happen that no point is safe, in which case the area is 0.

Input

The first line contains one integer n (3≤n≤1003 \le n \le 100), the number of mages in Bitocja. Each of the next n lines contains four integers axi,ayi,bxi,byia_{x_i}, a_{y_i}, b_{x_i}, b_{y_i} (−500≤axi,ayi,bxi,byi≤500-500 \le a_{x_i}, a_{y_i}, b_{x_i}, b_{y_i} \le 500). They mean that the towers of the i-th mage are at the points (axi,ayi)(a_{x_i}, a_{y_i}) and (bxi,byi)(b_{x_i}, b_{y_i}). All 2n points in the input are pairwise distinct.

Output

Print one real number, the area of the safe region. The allowed absolute or relative error is 10−810^{-8}. If the exact answer is AA and you print BB, the answer is accepted only when ∣A−B∣≤max⁡(A,1)⋅10−8|A - B| \le \max(A, 1) \cdot 10^{-8}.

Hint

The figure below shows the positions of the mage towers (black dots) and the safe region (grey shape). The point (1,32)(1, \frac{3}{2}) is safe. For every direction, there is a mage such that moving from the point in that direction brings it closer to both towers of that mage. The point (5,5)(5, 5) is not safe. Moving up from it moves away from all towers except the second tower of the fourth mage.

Examples1

  1. Example 1

    Input
    4
    0 0 0 -1
    -1 5 -2 2
    4 0 4 1
    2 2 6 6
    
    Expected output
    4.8000000000