EPY Dimokritos - 2004 Phase B, refactor of https://pastebin.com/jsnVFFCW

/*
this is a refactored solution of https://pastebin.com/jsnVFFCW

17ος Πανελλήνιος Διαγωνισμός Πληροφορικής
(Σχολικό Έτος 2004-5)

Θέμα Β' Φάσης: Δημόκριτος
Το Εθνικό Κέντρο Έρευνας Φυσικών Επιστημών "Δημόκριτος" της Ελλάδος, ονομάστηκε έτσι προς τιμή του Έλληνα «πατέρα» της ατομικής θεωρίας Δημόκριτου. Το Ε.Κ.Ε.Φ.Ε. διαθέτει πολλά Ερευνητικά Ινστιτούτα με περισσότερο ίσως γνωστό, το Ινστιτούτο Πυρηνικών Ερευνών. Μια από τις πολλές δραστηριότητες αυτού του Ινστιτούτου, είναι η παραγωγή ραδιενεργών σκευασμάτων που χρησιμοποιούνται για θεραπευτικούς, ερευνητικούς και παραγωγικούς σκοπούς. (π.χ. Ραδιοθεραπείες, Ισοτοπική Επισήμανση, Βιομηχανικές Ακτινογραφίες).

Τα ραδιενεργά σκευάσματα, τοποθετούνται σε ειδικά κιβώτια που δεν επιτρέπουν την εκπομπή ακτινοβολίας μέσα από αυτά. Κάθε κιβώτιο είναι εφοδιασμένο με συσκευή εκπομπής αναγνωριστικού σήματος (ραδιοταυτότητα). Τα κιβώτια αποθηκεύονται σε συγκεκριμένες θέσεις μιας επίπεδης αποθήκης. Μεταξύ των θέσεων αποθήκευσης, σχηματίζεται ένα κανονικό τετραγωνικό πλέγμα από διαδρόμους μετακίνησης. Ο κάθε κόμβος (διασταύρωση) των διαδρόμων μετακίνησης, προσδιορίζεται από ζεύγος συντεταγμένων (x, y). Στην οροφή της αποθήκης και στις «διασταυρώσεις» αυτού του πλέγματος, είναι τοποθετημένοι αισθητήρες υπερβραχέων, με σκοπό την αναγνώριση της θέσης των κιβωτίων. Ο κάθε αισθητήρας έχει συντεταγμένες (x, y) και ένα μοναδικό κωδικό αριθμό, που απεικονίζεται στο σύστημα ελέγχου. Αν ένα κιβώτιο βρεθεί σε μία διασταύρωση (κόμβο), τότε γίνεται αντιληπτό από το αισθητήρα που βρίσκεται ακριβώς πάνω από τον κόμβο και από τους οκτώ πλησιέστερους αισθητήρες προς το συγκεκριμένο κόμβο. Για παράδειγμα ένα κιβώτιο που θα περάσει από τη θέση (0, 0) γίνεται αντιληπτό από τους αισθητήρες: (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1) και τον (0, 0).

Τα κιβώτια μετακινούνται εντός της αποθήκης, με τη βοήθεια αυτόματου ρομποτικού οχήματος μεταφοράς. Προφανώς το ρομπότ μπορεί να μετακινείται στους διαδρόμους μεταξύ των κιβωτίων, κινούμενο πάντοτε παράλληλα ή κάθετα στον άξονα των x. Το ρομπότ ευρισκόμενο σε κάποιο κόμβο, μπορεί να κάνει μια από τις τέσσερις κινήσεις (Up), (Down), (Right), (Left). Κάθε κίνηση R αυξάνει τη τιμή της συντεταγμένης x (τετμημένη) κατά 1. Κάθε κίνηση U αυξάνει τη τιμή της συντεταγμένης y (τεταγμένη) κατά 1. Ως αρχή των κινήσεων του ρομποτικού συστήματος μεταφοράς, νοείται πάντοτε η αρχή των αξόνων (0,0). Στο επόμενο σχήμα, δίνεται ένα απλοποιημένο διάγραμμα διαδρομών με (11 x 11) διασταυρώσεις.

Να αναπτύξετε ένα πρόγραμμα το οποίο θα λαμβάνει σαν είσοδο τις κινήσεις των κιβωτίων και θα παράγει σαν έξοδο:

Α) Mε αύξουσα σειρά, τους κωδικούς αριθμούς των αισθητήρων που αναγνώρισαν τα κιβώτια.
Β) Τον αριθμό των διεγέρσεων που δέχθηκε κάθε αισθητήρας.
image

ΕΙΣΟΔΟΣ
Στην πρώτη γραμμή του αρχείου εισόδου dimokritos.in δίνεται ένας ακέραιος αριθμός N, (όπου 1 < N < 2,000,000), που αντιπροσωπεύει το πλήθος των αισθητήρων. Σε κάθε μία από τις ακόλουθες N γραμμές δίνονται οι συντεταγμένες των αισθητήρων με δύο ακέραιους αριθμούς, Χ και Υ που χωρίζονται με κενό χαρακτήρα, ( όπου -700 < x, y < 700). Η σειρά εμφάνισης των αισθητήρων ταυτίζεται με τον αντίστοιχο κωδικό αριθμό τους.

Στην επόμενη, (N+1)οστή γραμμή, δίνεται ο ακέραιος αριθμός Κ, (όπου 0 <= Κ <= 2,000,000) που δηλώνει το πλήθος των κινήσεων που πραγματοποίησε το ρομποτικό όχημα. Η τελευταία γραμμή περιέχει τους Κ χαρακτήρες που μας εμφανίζουν τη διαδρομή που πραγματοποίησε το όχημα. Οι χαρακτήρες αυτοί μπορεί να είναι U, D, R, L (Κεφαλαία Λατινικά) χωρίς κενό μεταξύ τους. Κάθε γραμμή συμπεριλαμβανομένης της τελευταίας τερματίζεται με τον χαρακτήρα νέας γραμμής και κανένας άλλος χαρακτήρας δεν υπάρχει μετά τον τελευταίο αριθμό κάθε γραμμής.

Σε κάθε περίπτωση το αρχείο εισόδου δεν μπορεί να ξεπερνά τα 2ΜΒ.

ΕΞΟΔΟΣ
Στο αρχείο εξόδου dimokritos.out θα πρέπει να γράψετε τους αριθμούς των αισθητήρων που έχουν «αντιληφθεί» το ρομποτικό όχημα καθώς και τον αριθμό (πλήθος) ων διεγέρσεων που έχει δεχτεί. Οι αριθμοί των αισθητήρων πρέπει να είναι ταξινομημένοι σε αύξουσα σειρά και κάθε αισθητήρας πρέπει να είναι σε με μια χωριστή γραμμή. Ο αριθμός των διεγέρσεων θα ξεχωρίζει με ένα κενό. Εάν κανένας αισθητήρας δεν «αντιλήφθηκε» το όχημα, στη πρώτη και μόνη γραμμή του αρχείου εξόδου πρέπει να γράψετε "-1".

(Παρατήρηση: Θεωρούμε ότι η παρακολούθηση κάθε μετακινούμενου κιβωτίου ξεκινάει όταν αυτό βρεθεί στην αρχή των αξόνων. Επίσης: Από τη στιγμή που κινηθεί το ρομποτικό όχημα μεταφοράς, ενεργοποιούνται και οι 9 αισθητήρες, γύρω και πάνω από την αρχή των αξόνων).

ΠΑΡΑΔΕΙΓΜΑΤΑ:
dimokritos.in
15
0 0
-1 0
-1 1
0 1
1 1
1 0
1 -1
0 -1
-1 -1
2 0
2 -1
2 1
-1 2
0 2
1 2
1
R

dimokritos.out
1 2
2 1
3 1
4 2
5 2
6 2
7 2
8 2
9 1
10 1
11 1
12 1

dimokritos.in
25
-2 -2
-2 -1
-2 0
-2 1
-2 2
-1 2
0 2
1 2
2 2
2 1
2 0
2 -1
2 -2
1 -2
0 -2
-1 -2
-1 0
-1 1
0 1
1 1
1 0
1 -1
0 -1
-1 -1
0 0
0

dimokritos.out
-1

*/

#include <stdio.h>
#include <stdlib.h>

#ifndef DIMOKRITOS
#define DIMOKRITOS

#define ZERO 0
#define NOMOVES "-1\n"
#define MEAN 700
#define MAX 1400
#define PENTIUM 86
#define NEGATIVE_MONAD "-1\n"

#define UNSIGNED "%u\n"

#define NUMBER "%d"
#define NUMBER_LF "%d\n"
#define NUMBERS "%d %d\n"

#define READ "r"
#define WRITE "w"

#define UP 'U'
#define DOWN 'D'
#define LEFT 'L'
#define RIGHT 'R'

#define IN "dimokritos.in"
#define OUT "dimokritos.out"
#endif

int x , y , *Xs , *Ys , gps [ MAX ][ MAX ] , grid ;
unsigned int id , sensors , moves ;
FILE *stream ;

int Up() {
    y++ ;
}

int Down() {
    y-- ;
}

int Left() {
    x-- ;
}

int Right() {
    x++ ;
}

void act_sensors () {
    ++gps[~-x][~-y], ++gps[  x][y], ++gps[-~x][-~y] ;
    ++gps[  x][~-y], ++gps[-~x][y], ++gps[~-x][-~y] ;
    ++gps[-~x][~-y], ++gps[~-x][y], ++gps[  x][-~y] ;
}

typedef int (*fptr)() ;

fptr fn_move[PENTIUM] ;

int main ( int argc, char *argv[] ) {

    fscanf ( stream = fopen ( IN , READ ) , UNSIGNED , &sensors ) ;
    Xs = ( int * ) malloc ( sensors * sizeof( int ) ) ;
    Ys = ( int * ) malloc ( sensors * sizeof( int ) ) ;
    for ( id = ZERO ; id < sensors ; ++id )
        fscanf ( stream , NUMBERS , &Xs[id] , &Ys[id] ) ;

    x = y = MEAN ;
    fn_move[UP] = Up, fn_move[DOWN] = Down, fn_move[LEFT] = Left, fn_move[RIGHT] = Right ;
    fscanf ( stream , UNSIGNED , &moves ) ;

    for ( act_sensors(), id = ZERO ; id < moves ; ++id ) {
        fn_move [ getc ( stream ) ] () ;
        act_sensors ();
    }
    fclose ( stream ) ;

    stream = fopen ( OUT , WRITE ) ;
    if ( moves > ZERO ) {
        for ( id = ZERO ; id < sensors ; ++id )
            if ( ( grid = gps[Xs[id] + MEAN][Ys[id] + MEAN] ) > ZERO )
                fprintf ( stream , NUMBERS , -~id , grid ) ;
    } else {
        fputs ( NOMOVES , stream ) ;
    }
    free ( Xs ), free ( Ys ) ;
    fclose ( stream ) ;

    return ZERO;
}