24ος ΠΔΠ B' Φάση Λυκείου
Ραδιοαστέρες (pulsars)
Στις 28 Nοεμβρίου 1967, μια μυστηριώδης ραδιοπηγή ανακαλύφθηκε στο γαλαξία μας. Αυτό που στην αρχή θεωρήθηκε δημιούργημα εξωγήινης νοημοσύνης, διαπιστώθηκε ότι οφείλεται στην περιοδική ακτινοβολία που εκπέμπουν ορισμένοι μυστηριώδεις αστέρες (ραδιοαστέρες - pulsars) που αργότερα αναγνωρίστηκαν ως αστέρες νετρονίων. Η χαρτογράφηση των αστέρων αυτών στο γαλαξία μας ξεκίνησε άμεσα, και γρήγορα έδωσε εξηγήσεις σε πολλά ερωτήματα για την εξέλιξη των αστέρων.
Η χαρτογράφηση γίνεται με την προβολή των ουράνιων συντεταγμένων (σφαιρικών) των ραδιοαστέρων στο καρτεσιανό επίπεδο. Για την κοσμολογία ιδιαίτερη σημασία έχει η εύρεση του ελάχιστου κυρτού πολυγώνου που περικλείει όλους τους ραδιοαστέρες που εντοπίζονται σε μια περιοχή του γαλαξία μας.
Το ελάχιστο κυρτό πολύγωνο είναι εκείνο το πολύγωνο που περιλαμβάνει όλα τα δοθέντα σημεία του επιπέδου μέσα του, είναι κυρτό, και έχει το μικρότερο δυνατό εμβαδό. Κυρτό σημαίνει ότι κάθε γωνία του είναι κυρτή και έτσι ισχύει η σημαντική ιδιότητα ότι κάθε γραμμή που ενώνει δύο σημεία του αρχικού συνόλου βρίσκεται ολόκληρη μέσα στο πολύγωνο. Για κάθε πεπερασμένο σύνολο σημείων υπάρχει πάντα ένα ελάχιστο κυρτό πολύγωνο. Το πρόβλημα της εύρεσης ελάχιστου κυρτού πολυγώνου (convex hull) εμφανίζεται συχνά στην πληροφορική και έχει πολλές εφαρμογές όπως μπορείτε να διαβάσετε στο http://en.wikipedia.org/wiki/Convex_hull.
Πρόβλημα
Nα αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες της IOI το οποίο θα δέχεται ως είσοδο τις συντεταγμένες \((X, Y)\) κάθε σημείου ενός συνόλου ραδιοαστέρων στο επίπεδο, και θα επιστρέφει τις κορυφές που συγκροτούν το ελάχιστο κυρτό πολύγωνο που περικλείει όλους τους ραδιοαστέρες. Nα θεωρήσετε ότι δεν υπάρχουν περισσότεροι από δύο ραδιοαστέρες πάνω στις πλευρές του πολυγώνου που να βρίσκονται στην ίδια ευθεία.
Αρχεία εισόδου
Το αρχείο εισόδου με όνομα pulsars.in είναι ένα αρχείο κειμένου με την εξής δομή: Στην πρώτη γραμμή περιέχει τον ακέραιο αριθμό \(N\) (\(10 \leq N \leq 1.000.000\)). Οι επόμενες \(N\) γραμμές έχουν, η κάθε μία, από ένα ζεύγος ακεραίων αριθμών \(X\), \(Y\) (\(0 \leq X, Y \leq 40.000\)). Οι αριθμοί αυτοί αντιστοιχούν στις συντεταγμένες κάθε ραδιοαστέρα στο επίπεδο.
Αρχεία εξόδου
Το αρχείο εξόδου με όνομα pulsars.out είναι ένα αρχείο κειμένου με την εξής δομή: Η πρώτη γραμμή περιέχει τον ακέραιο αριθμό \(M\) (\(3 \leq M \leq N\)), το πλήθος των σημείων που είναι κορυφές του ελάχιστου κυρτού πολυγώνου. Οι επόμενες \(M\) γραμμές έχουν, η κάθε μία, από έναν αριθμό \(P\) (\(1 \leq P \leq N\)). Ο αριθμός \(P\) αντιστοιχεί στη σειρά που έχει στο αρχείο εισόδου ο ραδιοαστέρας του οποίου η θέση στο καρτεσιανό επίπεδο αποτελεί κορυφή του ελάχιστου κυρτού πολυγώνου. Τα σημεία αυτά θα πρέπει να δίνονται σε αύξουσα σειρά και όχι με τη σειρά που εμφανίζονται στο κυρτό πολύγωνο.
Παρατηρήσεις
- Η σειρά εμφάνισης των ραδιοαστέρων που βρίσκονται στις κορυφές του ελάχιστου κυρτού πολυγώνου πρέπει είναι αύξουσα στο αρχείο εξόδου.
- Yπάρχει πάντα ένα ελάχιστο κυρτό πολύγωνο που περικλείει όλους τους ραδιοαστέρες.
- Σε όλα τα αρχεία ελέγχου, το αρχείο εξόδου θα είναι πάντα μοναδικό. Δηλαδή δεν θα υπάρχουν 3 σημεία που ανήκουν στο ελάχιστο κυρτό πολύγωνο και είναι συνευθειακά. Κάθε σημείο που βρίσκεται σε πλευρά του ελάχιστου κυρτού πολυγώνου είναι και κορυφή του.
- Δεν θα υπάρχουν ποτέ δύο ραδιοαστέρες στην ίδια ακριβώς θέση.
- Καμία υπόθεση δεν μπορεί να γίνει για τη σειρά με την οποία εμφανίζονται τα σημεία στο αρχείο εισόδου. Δεν θα είναι απαραίτητα ταξινομημένα.
Παραδείγματα αρχείων εισόδου - εξόδου
1o
| pulsars.in | pulsars.out |
|---|---|
| 10 1 5 2 10 5 5 3 8 6 10 8 7 9 10 8 11 9 3 3 1 |
6 1 2 7 8 9 10 |
Εξήγηση: Τα σημεία που δίνονται στο αρχείο εισόδου είναι 10 και φαίνονται στο παρακάτω σχήμα.
Τα σημεία που δίνονται στο αρχείο εισόδου εμφανίζονται με κόκκινο χρώμα, ενώ το ελάχιστο κυρτό πολύγωνο εμφανίζεται με γαλάζια διαγράμμιση. Όπως είναι φανερό, τα σημεία \(1\), \(2\), \(8\), \(7\), \(9\), \(10\) και μόνο αυτά συγκροτούν το ελάχιστο κυρτό πολύγωνο. Παρ’ όλο που στο πολύγωνο τα σημεία αυτά εμφανίζονται με την παραπάνω σειρά, στο αρχείο εξόδου τυπώνονται σε αύξουσα σειρά, δηλαδή \(1\), \(2\), \(7\), \(8\), \(9\), \(10\).
2o
| pulsars.in | pulsars.out |
|---|---|
| 10 1 7 9 7 1 1 9 1 2 4 8 4 6 5 6 3 4 3 4 5 |
4 1 2 3 4 |
Όρια
Mέγιστος χρόνος εκτέλεσης: \(5\) sec.
Όριο χρήσης μνήμης: \(64\) MB.
Στο \(50\%\) των δοκιμών που θα κάνουμε, θα είναι \(10 \leq N \leq 1.000\).