Welcome to ZOJ
Select Problem
ZOJ Problem Set - 2632
Knight in Corridor

Time Limit: 2 Seconds      Memory Limit: 65536 KB

A knight was trapped in a long and narrow corridor (2*n). The knight is asked to travel in the grids from one point and must return this point in the end. The path he passed will form a polygon; the edges of polygon should not touch each other. You are asked to compute the maximum area of the polygon. The following figure shows a series of possible moves of the knight, the point from A, B, C to D forms a polygon which area is 4. Note that from a point (x, y), the knight can only move to (x-2, y-1), (x-2, y+1), (x-1, y-2), (x-1, y+2), (x+1, y-2), (x+1, y+2), (x+2, y-1) or (x+2, y+1).


There are multiple test cases, each case consists of three integer, N, x and y (x <= N). N is the length of corridor which is not greater than 1000000000. (x, y) indicates the starting position of the knight. A test case with N = 0 indicates the end of input.


The maximum area (accurate to two fractional digits) of the polygon in each line. Assume the side length of grid is 1. If the required polygon does not exist, output "wuwuwu".

Sample Input:
4 0 1
4 0 0

Sample Output:

Author: ZHENG, Jianqiang
Source: ZOJ Monthly, December 2005
Submit    Status