Build Your Home

Interview

Time limit1sMemory limit128 MB

Summary

Compute and round the area of each given simple polygon, including degenerate cases with fewer than three vertices, until a terminating zero.

Level: Easy3 of 10
Topics: Geometry, Implementation, Math
Solved: No attempts yet

Problem

Mr. Tenant is going to buy a new house. More precisely, he is going to buy a piece of land and build his new house on it. To decide which piece of land to buy, Mr. Tenant needs a program that assigns a score to each piece. Each candidate piece of land has a polygonal shape (not necessarily convex), and Mr. Tenant wonders what the best score is. Among the possible scores he considered the number of vertices, the sum of angles, the minimum number of required guards, and so forth. In the end, Mr. Tenant decided that the score of a piece of land is simply its area. Your task is to write the scoring program.

Input

The input consists of several pieces of land. Each piece is a simple polygon (a polygon that does not intersect itself). A polygon description starts with a positive integer $k$ , followed by $k$ vertices, where each vertex is given by two floating-point coordinates $x$ and $y$ . The last vertex is connected by an edge back to the first vertex. The vertices of a polygon may be listed either clockwise or counterclockwise. The input ends with a single $0$ (the number zero).

Output

For each piece of land, print its score on exactly one line, rounded to the nearest integer. (A value of exactly one half is rounded up, but no such case occurs in the input.) Note: the program has to handle degenerate cases well, such as polygons with only one or two vertices.

Examples3

Example 1

Input

1   123.45 67.890
3   0.001 0   1.999 0   0 2
5   10 10   10 12   11 11   12 12   12.0 10.0
0

Expected output

0
2
3

Example 2
Input
```
4 0 0 0 10 10 10 10 0
0
```
Expected output
```
100
```
Example 3
Input
```
3 0 0 4 0 0 3
0
```
Expected output
```
6
```