Rent-A-Pixel

Time limit3sMemory limit128 MB

Summary

Compute the smallest row- and column-convex block set containing the given blocks and print its outline corners clockwise.

Level: Hard8 of 10
Topics: Geometry, Intervals, Sorting
Solved: No attempts yet

Problem

Harriet Emmel rents out space on her web page in blocks of 10 pixels by 10 pixels. The page is cut by grid lines drawn every 10 pixels, and anyone may rent blocks of that grid to post artwork, advertising, or anything else.

Emmel expected most customers to ask for a rectangle of blocks, but some had other ideas. An optician picked blocks shaped like a pair of eyeglasses, and an archery shop picked blocks shaped like a bullseye.

To keep the bookkeeping simple, Emmel decided that every purchase has to be one orthogonally convex set of blocks. Orthogonally convex means that every row and every column of the grid meets the set in either nothing or one contiguous run of blocks.

A customer picks whatever blocks they want, and Emmel then works out the smallest orthogonally convex region containing all of them and rents out that region. Write the program that computes this region.

Every request in the input gives a smallest region that is connected: for any two pixels of the region there is a path between them that steps up, down, left, or right and never leaves the region.

Input

The input holds several test cases.

The first line of a test case holds the number of blocks the customer picked, $n$ ( $1 \le n \le 10000$ ). One or more lines follow, holding $2n$ integers in the order $r_0\ c_0\ r_1\ c_1 \dots r_{n-1}\ c_{n-1}$ . Here $r_i$ and $c_i$ are the row and the column of the upper left pixel of block $i$ . Every coordinate is a multiple of 10 and satisfies $0 \le r_i, c_i \le 10^9$ . No coordinate pair appears twice inside one test case.

Each test case is chosen so that the smallest orthogonally convex region containing the blocks is a single connected polygon.

A line holding a single 0 ends the input.

Output

Print one line per test case. Start the line with Case k: , where $k$ is the test case number counting from 1. Then print the corners of the smallest orthogonally convex region, each one as its row number followed by its column number. Separate the numbers with single spaces and do not repeat the first corner at the end.

The first corner is the upper left pixel of the block that has the smallest row number, and among those the smallest column number. Starting there, walk once around the outline of the region in the clockwise direction: right along the top edge, down along the right edge, left along the bottom edge, up along the left edge. The walk stays on pixels that belong to the region. Print the row number and the column number of every pixel where the walk changes direction.

Examples1

Example 1

Input

30
20 20 20 30 20 40 20 50 20 60 20 70 20 80 20 90 20 100
20 110 20 120 20 130 20 140 20 150
30 20 30 70 30 100 30 150
40 20 40 70 40 100 40 150
50 30 50 40 50 50 50 60 50 110 50 120 50 130 50 140
28
80 60 80 70 80 80 80 90
90 50 90 100
100 40 100 70 100 80 100 110
110 40 110 60 110 90 110 110
120 40 120 60 120 90 120 110
130 40 130 70 130 80 130 110
140 50 140 100
150 60 150 70 150 80 150 90
0

Expected output

Case 1: 20 20 20 159 49 159 49 149 59 149 59 30 49 30 49 20
Case 2: 80 60 80 99 90 99 90 109 100 109 100 119 139 119 139 109 149 109 149 99 159 99 159 60 149 60 149 50 139 50 139 40 100 40 100 50 90 50 90 60