Convex Polygon Area

Problem #105

Tags: geometry practical

Who solved this?

You have probably already wrote the program for calculating Area of Triangle - let us now get acquainted with the extention of this problem - the calculation of area for arbitrary convex polygon.

Polygon is called convex if each of its angles is less than PI/2, or in other words, if any line connecting any pair of points belonging to it lies completely inside. This somewhat simplifies handling of such shapes.

You need to reduce this problem to one with triangles. We hope that pictures above may give you idea on three different approaches to do this.

Input data contain the number of vertices of the polygon.
Next lines contain a pair of numbers each - X and Y coordinates for the vertex (in correct CCW order).
Answer should contain the area of the shape surrounded by these points.


input data:
51 9
77 10
92 71
62 84
29 94

You need to login to get test data and submit solution.