50071. Attraction Order

I'm a slow walker, but I never walk backwards.

Task Description

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.

Hint

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.

Technical Limits

  • $1 \leq N \leq 2147483647$
  • $1 \leq M \leq 65536$
  • Your main program needs to include the header file, and use the structure Attraction to read the binary file.

main.c

1
2
3
4
#include "attraction.h"
/*
    Your code
*/

attraction.h

1
2
3
4
5
6
7
8
9
10
11
#ifndef _ATTRACTION_H
#define _ATTRACTION_H
 
#define MAXM 65536
#define MAXN 2147483647
 
typedef struct {
    int x, y;
} Attraction;
 
#endif

Input Format

./a.out [file_name]

There are only one line containing two integers, $N$ and $M$.

Output Format

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

./a.out p10160-0.dat

download p10160-0.dat

Input

3 5

Graph

p10160-0

Output

0 0
2 0
2 2
0 2
1 1

Sample Testcase 1

Comand Line Argument

./a.out p10160-1.dat

download p10160-1.dat

Input

4 10

Graph

p10160-1

Output

0 0
1 0
3 1
3 3
2 3
1 3
0 3
0 1
2 1
1 2

Discussion