405165: GYM101808 E Floods

You probably heard and even saw the heavy rains that flooded the streets of Damascus recently.

Shahhoud is wondering if he should go to university or not. He asked you to find out how much rainwater is filling his street.

To make things simple, you can imagine Shahhoud's street as a 2D polyline consisting of N points. A 2D polyline is a number of points such that every point is connected to the point before it by a line segment. It is guaranteed that any vertical line crosses the polyline in at most one point.

Rain falls from above the polyline down the y axis. Your task is to calculate the total area that keeps rainwater.

The image below describes the second sample test:

The first line contains a single integer T, the number of test cases.

Each test case starts with a line containing one integer N (1 ≤ N ≤ 10⁵), the number of points in the polyline that represents the street Shahhoud lives in.

The following N lines describe the points of the polyline. The i^th line contains two space separated integers x_i and y_i, the i^th point of the polyline. (0 ≤ x_i, y_i ≤ 10⁶). It is guaranteed that x_i < x_i + 1 for every 1 ≤ i < N.

For each test case, print one line containing the total area that keeps rainwater.

Your answer will be considered correct if the relative error is less than 10^- 6.

2
2
1 1
2 1
7
1 1
2 0
3 1
5 5
7 2
8 3
9 0

0.00000000
1.83333333