VM7WC '16 #6 Bronze - The Most Important Skill in Biology

View as PDF

Submit solution

Points: 3
Time limit: 1.0s
Memory limit: 64M

Problem types

Jeffrey is studying for his bio exam! One of the most crucial skills in biology is the ability to find the area of a shape, given only its points. Mr. White, Jeffrey's biology teacher, taught him a way to find that area: the Shoelace Theorem. The Shoelace Theorem only works if the shape is a simple polygon, i.e., it has a two dimensional shape consisting of straight, non-intersecting line segments that, when joined pair-wise, form a path. This means that exactly two edges meet at each vertex, no sides intersect, the number of edges are equal to the number of vertices, and the area enclosed by the shape will always be measurable.

The Shoelace Theorem works for simple polygons. However, since Jeffrey is horrible at biology, you have to help him implement the Shoelace Theorem. Since Jeffrey is similarly bad with decimal numbers, print the smallest integer not less than the area (the ceiling function).

Input Specification

On the first line will be an integer N (1 \le N \le 100), the number of points that define the shape. The next N lines will each contain two integers x and y (0 \le x, y \le 1000), denoting a Cartesian point (x, y) in the shape. The points will be given in counterclockwise order.

Output Specification

On a single line, print out the ceiling of the area of the shape defined by these N points.

Sample Input

3 4
5 6
9 5
12 8
5 11

Sample Output


Explanation for Sample Output

Here is an image of the given polygon:

Using the Shoelace Theorem, the area of this polygon is:

\displaystyle \mathbf A = \frac 1 2 \left|3 \times 11 + 5 \times 8 + 12 \times 5 + 9 \times 6 + 5 \times 4 - 4 \times 5 - 11 \times 12 - 8 \times 9 - 5 \times 5 - 6 \times 3\right| = \frac{60} 2 = 30


There are no comments at the moment.