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

View as PDF

Submit solution

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

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 \leq N \leq 100), the number of points that define the shape. The next N lines will each contain two integers x and y (0 \leq x, y \leq 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

5
3 4
5 6
9 5
12 8
5 11

Sample Output

30

Explanation for Sample Case

Here is an image of the given polygon:

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

\displaystyle  \mathbf{A} = {1 \over 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| = \dfrac{60}{2} = 30


Comments

There are no comments at the moment.