This page is still under construction.

Parts of this page are still being built. What you see may change.

Arable Area

Interview

Time limit1sMemory limit128 MB

Summary
Given a lattice polygon, count the unit grid squares fully contained inside it.
Level

Medium6 of 10

Topics
Geometry, Math, Number theory, Implementation
Solved
No attempts yet

Problem

The prime minister has recently bought a valuable piece of farmland lying in a valley, where the land forms a regular grid of unit square fields. A committee wants to verify the transaction, in particular whether the price paid matches the market value of the land. The market value is always defined as the number of unit square fields completely contained in the land.

Your task is to write a program that computes this market value. The purchased land forms a closed polygon whose vertices lie at the corners (lattice points) of the unit fields.

For example, the quadrilateral with vertices (1,1)(1, 1), (5,3)(5, 3), (5,4)(5, 4), and (3,5)(3, 5) fully contains exactly three unit square fields.

Input

The input consists of several scenarios. Each scenario starts with a line containing one integer NN (3≤N≤1003 \le N \le 100), the number of polygon vertices. Each of the next NN lines contains two integers XiX_i and YiY_i, the coordinates of one vertex. The vertices are listed in the order they appear along the boundary of the polygon. You may assume that every coordinate satisfies −100≤Xi,Yi≤100-100 \le X_i, Y_i \le 100 and that the boundary neither touches nor crosses itself.

The last scenario is followed by a line containing a single 00.

Output

For each scenario, output a single line with one integer — the number of unit squares completely inside the polygon.

Examples4

  1. Example 1

    Input
    4
    1 1
    5 3
    5 4
    3 5
    5
    3 3
    2 5
    3 4
    5 2
    1 1
    5
    0 0
    0 -50
    -50 -51
    -51 -50
    -50 0
    0
    
    Expected output
    3
    1
    2500
    
  2. Example 2

    Input
    4
    0 0
    1 0
    1 1
    0 1
    0
    
    Expected output
    1
    
  3. Example 3

    Input
    4
    0 0
    2 0
    2 2
    0 2
    0
    
    Expected output
    4
    
  4. Example 4

    Input
    3
    0 0
    4 0
    0 4
    0
    
    Expected output
    6