407176: GYM102697 147 Triangulation Rocks the Nation Again

This is a sigificantly harder version of a previous problem in the contest. We recommend you solve the earlier problem first.

You're given the coordinates of an $$$n$$$-sided polygon. The polygon is not necessarily a regular polygon (the sides and angles are not necessarily equal), but the polygon is guaranteed to be convex (the polygon will not contain any angles greater than or equal to 180 degrees).

Given this information, figure out the area of the given polygon.

The first line of input consists of a positive integer $$$n$$$ greater than three: the number of sides of the polygon.

The next $$$n$$$ lines each contain two space-separated integers: the $$$x$$$ and $$$y$$$ coordinates of each point of the polygon.

None of the sides of the polygon will be completely vertical.

Output a single decimal number $$$a$$$: the area of the given $$$n$$$-sided polygon. Remember, the polygon is guaranteed to be a convex polygon.

4
0 5
5 0
0 -5
-5 0

50.0

5
6 6
4 3
2 1
1 5
3 7

15.5

4
1 1
2 3
3 6
4 9

1.0

It might help to use your code from the easier version