21ος ΠΔΠ B' Φάση Γυμνασίου
Αναχαιτίσεις στο Αιγαίο (airforce)
Η Πολεμική Αεροπορία επιτελεί ένα πολύπλευρο έργο. Σε καιρό ειρήνης, λαμβάνει μέρος σε πληθώρα αποστολών έρευνας και διάσωσης, αεροδιακομιδών, αεροπυρόσβεσης και ειρηνευτικών αποστολών σε κάθε γωνιά του πλανήτη. Ο κύριος όμως ρόλος της, είναι η προάσπιση του Ελληνικού εναέριου χώρου από παραβιάσεις. Σχεδόν καθημερινά, Ελληνικά μαχητικά αεροσκάφη αναλαμβάνουν αποστολές αναγνώρισης και αναχαίτισης ξένων αεροσκαφών. Σε αρκετές περιπτώσεις οι αναχαιτίσεις εξελίσσονται σε εμπλοκές. Οι συνθήκες σε αυτές τις περιπτώσεις είναι ιδιαίτερα δυσμενείς για δύο κυρίως λόγους: Τα μαχητικά αεροσκάφη έχουν το ελάχιστο δυνατό εκπεμπόμενο σήμα (σε όλο το φάσμα των ραδιοσυχνοτήτων) για να μην αναγνωρίζονται εύκολα, και είναι γενικά του ιδίου τύπου με τα αντίπαλα αεροσκάφη.
Η ασφάλεια των πτήσεων, καθιστά απαραίτητα συστήματα που βοηθούν στον έλεγχο και τη διαχείριση του εναέριου χώρου από τους αρμόδιους φορείς. Προς την κατεύθυνση αυτή, το σημαντικότερο ρόλο παίζουν τα συστήματα παροχής αξιόπιστης και συγκεντρωτικής εικόνας της εναέριας κυκλοφορίας του χώρου ευθύνης τους (FIR). Ιδιαίτερης σημασίας είναι τα συστήματα αναγνώρισης εγγυτέρου ίχνους, που αποσκοπούν στην έγκαιρη ενημέρωση των χειριστών σχετικά με την κατάσταση του αεροπορικού χώρου δράσης τους. Τα συστήματα αυτά πρέπει να μπορούν να αναγνωρίζουν το συντομότερο δυνατόν τα πλησιέστερα αεροσκάφη.
Πρόβλημα
Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΙΟΙ το οποίο, αφού διαβάσει τα δεδομένα της εξόδου ενός ψηφιακού ραντάρ, με τη μορφή τριάδας δεδομένων που αντιστοιχούν σε κάθε εντοπισθέν ίχνος, θα εντοπίζει και θα επισημαίνει τα ίχνη με τη μικρότερη μεταξύ τους απόσταση, άρα το μεγαλύτερο κίνδυνο σύγκρουσης (Το μοναδικό κριτήριο εντοπισμού είναι η ελάχιστη απόσταση και όχι και άλλα όπως η ταυτότητα των αεροσκαφών.)
Αρχεία εισόδου
Τα αρχεία εισόδου με όνομα airforce.in είναι αρχεία κειμένου με την εξής δομή: Στην πρώτη γραμμή έχουν έναν ακέραιο αριθμό \(N\) (\(10 \leq N \leq 1.000\)) που αντιστοιχεί στον αριθμό των εντοπισθέντων ιχνών. Οι επόμενες \(N\) γραμμές έχουν από μία τριάδα αριθμών \(x\), \(y\), \(z\) (\(-1.000 \leq x, y, z \leq 1.000\)) που αντιστοιχούν στις τρεις συντεταγμένες ενός ορθοκανονικού συστήματος. Οι αριθμοί χωρίζονται με ένα κενό.
Αρχεία εξόδου
Τα αρχεία εξόδου με όνομα airforce.out είναι αρχεία κειμένου με την εξής δομή: Αποτελούνται από μια μόνο γραμμή που έχει δύο αριθμούς χωριζόμενους με ένα κενό. Οι αύξοντες αριθμοί (θέσεις \(N-1\), στο αρχείο airforce.in) των ιχνών που έχουν τη μικρότερη απόσταση.
Παραδείγματα αρχείων εισόδου - εξόδου
1o
| airforce.in | airforce.out |
|---|---|
| 10 100 2 0 10 3 0 50 6 0 70 7 0 90 8 0 110 9 0 130 10 0 150 11 0 150 12 0 1 3 2 |
8 9 |
2o
| airforce.in | airforce.out |
|---|---|
| 15 1 1 1 1 1 2 1 2 3 1 2 4 1 2 5 1 3 6 1 3 7 1 4 8 1 4 9 1 5 11 1 5 13 1 6 15 1 6 17 1 7 18 1 7 20 |
1 2 |
Παρατηρήσεις
- Απόσταση δύο σημείων στον τρισδιάστατο χώρο d=((x2-x1)^2+(y2-y1)^2+(z2-z1)^2)^1/2
- Ο χρόνος υπολογισμού είναι ζωτικής σημασίας για αεροπορικές επιχειρήσεις. Υλοποιήσεις λοιπόν με μικρότερο χρόνο θα έχουν μεγαλύτερη βαρύτητα σε περίπτωση ισοβαθμιών
- Η μέγιστη απόσταση στην οποία μπορούν να αναγνωριστούν δύο αεροσκάφη είναι 10.000 μονάδες απόστασης
- Αν τα δύο εγγύτερα αεροσκάφη είναι το 3ο και το 4ο το αρχείο airforce.out θα έχει τις τιμές [3 4] και όχι [4 3]
- Δεν υπάρχουν περισσότερα από ένα ζεύγη αεροσκαφών με την ίδια μικρότερη απόσταση μεταξύ τους
- Μέγιστος χρόνος εκτέλεσης: 5 sec.
- Μέγιστη επιτρεπτή χρήση μνήμης: 5 MB