Arable Area
InterviewTime limit1sMemory limit128 MB
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 , , , and fully contains exactly three unit square fields.
Input
The input consists of several scenarios. Each scenario starts with a line containing one integer (), the number of polygon vertices. Each of the next lines contains two integers and , 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 and that the boundary neither touches nor crosses itself.
The last scenario is followed by a line containing a single .
Output
For each scenario, output a single line with one integer — the number of unit squares completely inside the polygon.