reconstructor his traveling order Help a traveler to reconstructor his traveling

Question

reconstructor his traveling order

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 xx and yy coordinate between 0and N1. The traveler starts from (0,0) and goes east to(N1,0), then he goes north to (N1,N1), then west to (0,N1), 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 MM 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

1N2147483647

1M65536

Your main program needs to include the header file, and use the structure Attraction to read the binary file.

attraction.h

#ifndef _ATTRACTION_H

#define _ATTRACTION_H

#define MAXM 65536

#define MAXN 2147483647

typedef struct {

    int x, y;

} Attraction;

#endif

sample: p10160-1.dat

https://judgegirl.csie.org/downloads/p10160-1.dat

input :4 10

output:

0 0

1 0

3 1

3 3

2 3

1 3

0 3

0 1

2 1

1 2

Explanation / Answer

main.cpp

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "attraction.h"

typedef struct {
   unsigned long long idx;
   int x, y;
} V;
static inline int min(int x, int y) {return x < y ? x : y;}
static int cmp(const void *x, const void *y) {
   V *a = (V *) x, *b = (V *) y;
   if (a->idx < b->idx)   return -1;
   return 1;
}
int main(int argc, char *argv[]) {
   assert(argc > 1);
   static Attraction A[MAXM];
   static V T[MAXM];
   int n, m;
   scanf("%d %d", &m, &n);
   {
       FILE *fin = fopen(argv[1], "rb");
       assert(fin != NULL);
       n = fread(A, sizeof(Attraction), MAXM, fin);
       fclose(fin);
   }
   for (int i = 0; i < n; i++) {
       int x = A[i].x, y = A[i].y;
       unsigned long long c = min(min(x, m-1-x), min(y, m-1-y));
       unsigned long long idx = (c) * (8LL*(m-1)-2*c+2)/2;
       if (y == c)
           idx += x-c;
       else if (x == m-1-c)
           idx += y-c + (m-2*c-1);
       else if (y == m-1-c)
           idx += m-c-1-x + 2*(m-2*c-1);
       else
           idx += m-c-1-y + 3*(m-2*c-1);
       T[i].x = x, T[i].y = y, T[i].idx = idx;
   }
   qsort(T, n, sizeof(V), cmp);
   for (int i = 0; i < n; i++)
       printf("%d %d ", T[i].x, T[i].y);
   return 0;
}

attraction.h

#ifndef _ATTRACTION_H
#define _ATTRACTION_H

#define MAXM 65536
#define MAXN 2147483647

typedef struct {
    int x, y;
} Attraction;

#endif

Related Questions

Navigate

• Browse (All)
• Browse R
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.