21ος ΠΔΠ Γ' Φάση
Aegean (aegean)
[ Μονάδες]
To Πανεπιστήμιο Αιγαίου έχει θέσει σε λειτουργία το σύστημα παρακολούθησης σε πραγματικό χρόνο της εμπορικής ναυσιπλοΐας στο Αιγαίο (http://syros-observer.aegean.gr/ais/). Το σύστημα βασίζεται στην καταγραφή του σήματος UHF (Ultra High Frequency) κάθε πλοίου, όπως αυτό λαμβάνεται από ένα ορθοκανονικό δίκτυο παράκτιων κεραιών.
Το Κέντρο Διαχείρισης Δικτύων του Αριστοτελείου Πανεπιστημίου Θεσσαλονίκης (Α.Π.Θ.) και το τμήμα Πληροφορικής και Τηλεπικοινωνιών του Εθνικού και Καποδιστριακού Πανεπιστημίου Αθηνών (Ε.Κ.Π.Α) ανέλαβαν να αναπτύξουν το κατάλληλο λογισμικό, ώστε να υπάρχει ψηφιακή απεικόνιση πραγματικού χρόνου της εποπτευόμενης περιοχής. Η βασική παραδοχή του συστήματος, είναι ότι η θέση κάθε πλοίου αναγνωρίζεται από την ισχύ του λαμβανόμενου, από ένα ζεύγος κεραιών σήματος (επειδή είναι δυνατόν σε κάθε άξονα να λαμβάνουν την ταυτότητα κάθε πλοίου περισσότερες από μία κεραίες, οδηγείται σε επεξεργασία μόνο το ισχυρότερο σήμα).
Στο παρακάτω σχήμα φαίνεται ένα τέτοιο παράδειγμα: Με έντονα μαύρα γράμματα εμφανίζεται η στάθμη του σήματος που λαμβάνεται σε κάθε κεραία. Είναι φανερό ότι:
-
Το σήμα είναι τόσο μικρότερης στάθμης όσο μακρύτερα βρίσκεται το πλοίο. Η ισχύς \(I\) δηλαδή του λαμβανομένου σήματος προκύπτει από την σχέση \(I = N – X\) (για σύστημα \(N \times N\) κεραιών, το εγγύτερο στην κεραία πλοίο έχει σήμα στάθμης \(N\) και το πλέον απομακρυσμένο 1).
-
Όταν τα πλοία κινούνται σε σειρά ή κατά μέτωπο η αντίστοιχη κεραία (κατά την αρχική φάση του έργου) δέχεται μόνο σήμα από το εγγύτερο πλοίο. (Στο σχήμα μας, η δεύτερη οριζόντια κεραία λαμβάνει μόνο το σήμα από το πλοίο με συντεταγμένες \([2, 4]\)). Κατά τη φάση δοκιμών του συστήματος, έγινε η αντίστροφη διαδικασία. Με βάση τη γνωστή θέση συγκεκριμένων πλοίων, έγινε καταγραφή των σημάτων που έφταναν στις κεραίες λήψεως.
| 10 | 1 | * | |||||||||
| 9 | |||||||||||
| 8 | |||||||||||
| 7 | |||||||||||
| 6 | 9 | * | |||||||||
| 5 | 9 | * | |||||||||
| 4 | 9 | * | |||||||||
| 3 | |||||||||||
| 2 | |||||||||||
| 1 | |||||||||||
| 7 | 1 | ||||||||||
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
Πρόβλημα
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο: Αφού διαβάσει τις συντεταγμένες των πλοίων που εκπέμπουν σήμα, θα επιστρέφει την υψηλότερη στάθμη του σήματος που λαμβάνουν οι κεραίες πρώτα στον οριζόντιο και ακολούθως στον κάθετο άξονα.
Αρχεία εισόδου
Τα αρχεία εισόδου με όνομα aegean.in είναι αρχεία κειμένου με την εξής δομή. Στην πρώτη γραμμή υπάρχει ένας ακέραιος αριθμός \(N\) (\(0 \leq N \leq 199.998\)) που εκφράζει τον αριθμό των πλοίων που εκπέμπουν σήμα. Ακολουθούν \(N\) γραμμές σε κάθε μία από τις οποίες υπάρχουν οι συντεταγμένες των πλοίων (πρώτα οι τεταγμένες). Στο παράδειγμά μας οι \([2, 4]\), \([2, 5]\), \([2, 6]\), \([10, 10]\).
Αρχεία εξόδου
Τα αρχεία εξόδου με όνομα aegean.out είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν έναν αριθμό \(\Delta\) (\(10 \leq \Delta \leq 999.999.999\)) τις διαστάσεις (\(\Delta \times \Delta\)) της επιτηρούμενης θάλασσας (όλα τα ανιχνεύσιμα πλοία πρέπει να περικλείονται μέσα στις διαστάσεις της επιτηρούμενης θάλασσας.) Στη δεύτερη γραμμή έχουν δύο αριθμούς \(M_1\), \(M_2\) (χωρισμένους με ένα κενό) οι οποίοι εκφράζουν αντίστοιχα τον αριθμό των οριζόντιων και των κάθετων κεραιών που εντόπισαν πλοίο (\(0 \leq M_1, M_2 \leq \Delta\)). Στις επόμενες \(M_1\) γραμμές εμφανίζονται με αύξουσα σειρά οι αριθμοί και η αντίστοιχη στάθμη σήματος των οριζόντιων κεραιών που εντόπισαν πλοίο. Στις επόμενες \(M_2\) γραμμές εμφανίζονται με αύξουσα σειρά οι αριθμοί και η αντίστοιχη στάθμη σήματος των κάθετων κεραιών που εντόπισαν πλοίο. Σε όλες τις κεραίες ο αύξων αριθμός τους και η στάθμη σήματος, χωρίζονται μεταξύ τους με ένα κενό.
Παραδείγματα αρχείων εισόδου - εξόδου
1o
| aegean.in | aegean.out |
|---|---|
| 4 2 4 2 5 2 6 10 10 |
10 2 4 2 7 10 1 4 9 5 9 6 9 10 1 |
Παρατηρήσεις
- Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
- Μέγιστος χρόνος εκτέλεσης: 5 sec.