407679: GYM102870 I Irregular Shape of Orz Pandas

I. Irregular Shape of Orz Pandastime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Some Orz Pandas are watching Master Ma's video and laughing. Master Ma is a famous combat trainer. In the video he is presenting his signature move, the Five Continous Whips of Lightning. He has sketched the move on a blackboard. The shape of the sketch is very irregular but can be approximated as a polygon.

Master Ma believes the power of the Five Continous Whips of Lighting is proportional to the area of this polygon. While the Orz Pandas are laughing, they also want to know the value of this area.

Input

There are multiple test cases. Please process until EOF.

For each test case, the first line contains one integer $$$n$$$, the number of vertices of the polygon. The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$, the Cartesian coordinates of the $$$i$$$-th vertex.

The $$$i$$$-th edge of the polygon is the segment connecting the $$$i$$$-th vertex and the $$$(i+1)$$$-th vertex. The $$$n$$$-th edge is the segment connecting the $$$n$$$-th and the first vertex.

It's guaranteed that $$$3 \leq n \leq 10^3$$$, $$$-10^9 \leq x_i, y_i \leq 10^9$$$, and the sum of $$$n$$$ of all test cases in the input file will not exceed $$$10^4$$$.

Since Master Ma's move is too irregular, the polygon may be non-convex. But it's guaranteed that the polygon is simple: each line segment endpoint is shared by exactly two segments, and the segments do not otherwise intersect. It's also guaranteed that all vertices are unique.

Output

For each test case output one line containing the area of the polygon. The area should be rounded up to exactly two decimal places after the point.

This problem is not special judged.

ExamplesInput

3
1 1
4 5
1 4

Output

4.50

Input

6
0 0
1000000000 0
1000000000 999999999
999999999 999999999
999999999 1000000000
0 1000000000

Output

999999999999999999.00

Input

12
-1000000000 -1000000000
1000000000 -1000000000
1000000000 1000000000
-1000000000 1000000000
-1000000000 -999999998
999999998 -999999998
999999998 -999999997
-999999999 -999999997
-999999999 999999999
999999999 999999999
999999999 -999999999
-1000000000 -999999999

Output

9999999992.00

Input

12
-1000000000 1000000000
1000000000 1000000000
1000000000 -1000000000
-1000000000 -1000000000
-1000000000 999999998
999999998 999999998
999999998 999999997
-999999999 999999997
-999999999 -999999999
999999999 -999999999
999999999 999999999
-1000000000 999999999

Output

9999999992.00

Note

To reduce the number of "Wrong Answer", the Orz Pandas added several additional examples. Use them wisely.