Carrot Field
Time limit1sMemory limit1024 MB
Count lattice points within rope reach of a horse tied at the stable corner, where the rope cannot pass through the w by h rectangle.
- Level
Medium7 of 10
- Topics
- Geometry, Math, Combinatorics, Implementation
- Solved
- No attempts yet
Problem
In the middle of an infinitely large carrot field there is a rectangular stable whose sides are parallel to the and axes. As in the left figure of Figure B.1, a horse is tied to the post at the lower left corner of the stable, and all four corners of the stable lie on lattice points. The distance between two lattice points that are adjacent horizontally or vertically is . The rope tying the horse has finite length . A carrot is planted at every lattice point of the carrot field. Assume the horse can eat every carrot planted within the reach of the rope.
When the stable is 11 × 6 and the rope has length 9, the carrots the horse can eat are marked with dots in the right figure of Figure B.1. The horse and the rope cannot enter the stable, and no carrots are planted on the boundary or in the interior of the stable.

Figure B.1 (left) The stable and a horse tied with a rope of length 9. (right) All carrots the horse can eat (dots).
Given the stable size and the length of the rope tying the horse, that is, the three integers , , , write a program that finds the maximum number of carrots the horse can eat. Note that if the distance between a lattice point and the post is exactly , the horse can eat the carrot at that lattice point.
Input
The input comes from standard input. The first line gives the three positive integers , , () representing the stable size and the rope length.
Output
The output goes to standard output. On the first line, print as an integer the maximum number of carrots the horse can eat under the given conditions.