
ZOJ Problem Set  2632
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 (x2, y1), (x2, y+1), (x1, y2), (x1, y+2), (x+1, y2), (x+1, y+2), (x+2, y1) or (x+2, y+1). Input: 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. Output: 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 0Sample Output: 4.00 wuwuwu Author: ZHENG, Jianqiang Source: ZOJ Monthly, December 2005 