Help a traveler to reconstructor his traveling order.
A traveler travels through a country, which consists of $N$ by $N$ grid points. Each grid point has both $x$ and $y$ coordinate between $0$ and $N-1$. The traveler starts from $(0,0)$ and goes east to $(N-1,0)$, then he goes north to $(N-1,N-1)$, then west to $(0,N-1)$, then south to $(0,1)$. After that he goes east again and repeat this counter-clockwise order until he has traveled through all grid points. Note that $N$ could be as large as $2147483647$.
The traveler records the attraction he went through in this country. There are $M$ attractions in this country and each one locates in a distinct grid point. Whenever the traveler encounters an attractions, he will record the $x$ and $y$ coordinates (as a struct) in a binary file. After the traveler goes through all grid points, he has a file of $M$ attractions.
Unfortunately the hard disk storing the file breaks down and the traveler can only recover a broken file. The file has all the attraction locations, but the order is completely wrong. Now given this broken file, please help the traveler reconstruction the order of attractions he has traveled. The name of the file will be given as a command line argument.
Note that $N$ is so large you cannot possibly use an $N$ by $N$ array to store the locations of the attractions. Instead you should sort the locations of these attractions according to which "circle" they belong to. For example, the first circle consists of moving east, north, west, and south directions. The we have the second circle, which also consists of moving east, north, west, and south directions. A simple observation is that an attraction appears in an outer circle will always appear before any attraction appearing in inner circles. The next important observation is that one can determine which circle an attraction belong to by computing the minimum of the difference in x and y coordinates to the four boundaries of the country. The final observation is that one can determine which direction (among the four) an attraction belongs to by noting which boundary (among the four) has the minimum difference.
- $1 \leq N \leq 2147483647$
- $1 \leq M \leq 65536$
- Your main program needs to include the header file, and use the structure
Attractionto read the binary file.
#define MAXM 65536
#define MAXN 2147483647
There are only one line containing two integers, $N$ and $M$.
There are $M$ lines. Each line is a position of an attraction, and the output order is the order of traveler.
Sample Testcase 0
Comand Line Argument
Sample Testcase 1
Comand Line Argument