Some countries are literarily known by their shapes. For example, France is sometimes referred to as ‘the hexagon’, Italy is called ‘the boot’ and Portugal is known as ‘the rectangle by the ocean’ (the Atlantic Ocean, of course). Given our mathematical background, we are curious to know exactly which rectangle we are talking about when we say that Portugal is a rectangle. More precisely, we want to compute the rectangle that best fits the contour of the Portuguese map (not counting the islands). By definition, that would be a rectangle with horizontal basis for which at least three of the four corners lie on the contour of the map and whose area is closest to the area of the map (either from above or from below). In general, we are given a closed line on a plane, which we shall call here a ‘contour’ (see below for a better characterization of our contours), and we want to discover a rectangle with horizontal and vertical sides having at least three of the four corners on given points of the contour and such that its area is closest to the area inside the contour. For this task, each contour is described by a sequence of contiguous segments, each segment con- necting a point with integer coordinates to one of the eight points with integer coordinates nearby, horizontally, vertically, or diagonally. The contour is closed and does not touch itself. Here is an example, whose area is 12.5: This figure corresponds to the data presented in the Sample Input and Sample Output sections below (assuming the lower left corner of the grid has coordinates (0, 0)). The shaded area represents the solution. Input The first line of input contains C (0 < C < 100), the number of test cases that follows. The first line of each test case contains one integer, N, representing the number of points that define the contour for that test case, 4 ≤ N ≤ 256. Each of the N following lines contains two integers, X and Y , separated by a space, defining the x and y coordinates of a point along the contour. Note that X and Y can be positive, negative or zero. Successive points Pi and Pi+1 (with 1 ≤ i < N) define a segment that belongs to the contour. The last segment is defined by PN and P1, thus closing the contour. The x coordinates of Pi and Pi+1 and also of PN and P1 differ by at most 1 (in absolute value) and so do the y coordinates. All points are distinct.
2/2 Output The output file has C lines, one for each test case. Each line has five numbers, separated by a space. The first of these five numbers represents the area of the contour and should be written with exactly one decimal place; the remaining four numbers are integers representing the coordinates of the lower left corner and of the upper right corner of the computed rectangle. The computed rectangle has at least three of its four corners on the points given to define the contour and its area is as close as possible to the area within the contour. If more than one rectangle meets these requirements, your program should provide the one whose sequence of coordinates is lexicographically the least. Sample Input 2 17 12 23 14 15 25 35 45 55 54 44 43 52 51 42 41 31 21 8 00 10 20 30 40 31 22 11 Sample Output 12.5 1 1 4 5 4.0 0 0 2 2