Στα χνάρια Δημοσιεύω προβλήματα από το κομμάτι Αλγόριθμος (Κλασσικός προγραμματισμός αθλημάτων. Σε μιάμιση ώρα χρειάζεται να λύσετε τρία προβλήματα σε Java, C#, C++ ή Python.)
1. Πίτα για έξι
Δήλωση προβλήματος
Το χρονικό όριο είναι 4 δευτερόλεπτα.
Έχεις μια πίτα. Όταν το δούμε από ψηλά, το κέικ έχει το σχήμα ενός (αυστηρά) κυρτού πολυγώνου. Σας δίνονται οι συντεταγμένες των κορυφών σε X και Y ακέραιους αριθμούς.
Έχεις πέντε φίλους. Θέλετε να χωρίσετε την πίτα σε έξι κομμάτια ίσου εμβαδού (αλλά όχι απαραίτητα το ίδιο σχήμα). Φυσικά, ο καθένας μπορεί να το κάνει σε πέντε περικοπές, αλλά μόνο ένας επαγγελματίας μπορεί να το κάνει σε τρεις περικοπές.
Βρείτε τρία κοψίματα σε ευθείες γραμμές σε ένα σημείο που θα χωρίσει την πίτα σε έξι ίσα μέρη. Εκτύπωση {x, y, d1, d2, d3}, όπου (x, y) είναι το κοινό σημείο και των τριών περικοπών και d1, d2, d3 είναι οι γωνίες κατεύθυνσης των περικοπών σε ακτίνια.
ΟρισμόςΤάξη: CakeForSix
Μέθοδος: κοπή
Παράμετροι: int[], int[] Επιστρέφει: double[] Υπογραφή μεθόδου: double[] cut(int[] x, int[] y)
(βεβαιωθείτε ότι η μέθοδός σας είναι δημόσια)
Σημειώσεις
- Η θετική κατεύθυνση κατά μήκος του άξονα x είναι 0 (ακτίνια), η θετική κατεύθυνση κατά μήκος του άξονα y είναι pi/2 (ακτίνια).
- Μια περικοπή στην κατεύθυνση d είναι παρόμοια με μια περικοπή στην κατεύθυνση pi*k+d για οποιονδήποτε ακέραιο αριθμό k.
- Μπορείτε να εξάγετε οποιεσδήποτε κατευθύνσεις, δεν χρειάζεται να είναι από [0, pi).
- Ο γκρέιντερ θα υπολογίσει το εμβαδόν των έξι κομματιών κέικ σας σε διπλά. Η απάντηση θα γίνει δεκτή εάν η σχετική ή απόλυτη διαφορά μεταξύ τους είναι μικρότερη από 10^(-4).
- Πιο συγκεκριμένα, αφήστε το X και το Y να είναι το μικρότερο και μεγαλύτερο από τα έξι εμβαδά σας που υπολογίζονται από τον βαθμολογητή. Τότε η απάντησή σας θα γίνει δεκτή εάν Υ
- (Η αρχική έκδοση του προβλήματος χρησιμοποιούσε ακρίβεια 1e-7 αντί για 1e-4. Για την επίλυση αυτού του προβλήματος στο αρχείο, το όριο ακρίβειας μειώθηκε λόγω της παρουσίας περιπτώσεων κλήσης που πιθανότατα θα καθιστούσαν το πρόβλημα άλυτο με ακρίβεια του 1e-7. Σε έναν ιδανικό κόσμο, τα όρια δεν επιτρέπουν τέτοιες περιπτώσεις και εξακολουθούν να απαιτούν υψηλή ακρίβεια, επομένως η επίλυση του προβλήματος με κάποια γενική αριθμητική βελτιστοποίηση δεν είναι εύκολη.)
Περιορισμοί
- Το x περιέχει από 3 έως 50 στοιχεία συμπεριλαμβανομένων.
- Το y περιέχει τον ίδιο αριθμό στοιχείων με το x.
- όλες οι συντεταγμένες μεταξύ 0 και 10 συμπεριλαμβανομένων
- Τα x και y ορίζουν ένα κυρτό πολύγωνο αριστερόστροφα.
πρωτότυπο στα αγγλικά
Δήλωση προβλήματος
Το χρονικό όριο είναι 4 δευτερόλεπτα.
Έχετε μια τούρτα. Από ψηλά, το κέικ είναι ένα (αυστηρά) κυρτό πολύγωνο. Σας δίνονται οι συντεταγμένες των κορυφών του στο int[]sx και y.
Έχεις πέντε φίλους. Τώρα θέλετε να κόψετε το κέικ σε έξι κομμάτια ίσης επιφάνειας (αλλά όχι απαραίτητα ίσου σχήματος). Φυσικά, ο καθένας μπορεί να το κάνει αυτό σε πέντε περικοπές — αλλά μόνο ένας αληθινός επαγγελματίας μπορεί να το κάνει σε τρεις!
Βρείτε τρία κοψίματα σε ευθεία γραμμή που περνούν από το ίδιο σημείο που κόβετε το κέικ σε έξι εξίσου μεγάλα μέρη. Επιστροφή {x, y, d1, d2, d3}, όπου (x, y) είναι το κοινό σημείο των τριών περικοπών και d1, d2, d3 είναι οι κατευθύνσεις τους σε ακτίνια.
Ορισμός
Τάξη: CakeForSix
Μέθοδος: κοπή
Παράμετροι: int[], int[] Επιστρέφει: double[] Υπογραφή μεθόδου: double[] cut(int[] x, int[] y)
(βεβαιωθείτε ότι η μέθοδός σας είναι δημόσια)
Notes
— Η θετική κατεύθυνση κατά μήκος του άξονα x είναι 0 (ακτίνια), η θετική κατεύθυνση κατά μήκος του άξονα y είναι pi/2 (ακτίνια).
— Μια τομή προς την κατεύθυνση d είναι ίδια με την τομή στην κατεύθυνση pi*k+d για οποιονδήποτε ακέραιο αριθμό k.
— Μπορείτε να επιστρέψετε οποιεσδήποτε οδηγίες, δεν χρειάζεται να είναι από [0,pi).
— Ο βαθμολογητής θα υπολογίσει τα εμβαδά των έξι κομματιών κέικ σας σε διπλά. Η απάντηση θα γίνει δεκτή εάν η σχετική ή απόλυτη διαφορά μεταξύ τους είναι μικρότερη από 10^(-4).
— Πιο συγκεκριμένα, αφήστε το X και το Y να είναι το μικρότερο και το μεγαλύτερο από τα έξι πεδία σας, όπως υπολογίζονται από τον βαθμολογητή. Στη συνέχεια, η απάντησή σας θα γίνει αποδεκτή εάν Y < max( X + 10^(-4), X * (1+10^(-4)) ).
— (Η αρχική έκδοση του προβλήματος χρησιμοποιούσε ακρίβεια 1e-7 αντί για 1e-4. Για την επίλυση αυτού του προβλήματος στο αρχείο, το όριο ακρίβειας μειώθηκε λόγω της ύπαρξης περιπτώσεων πρόκλησης που πιθανότατα καθιστούν την εργασία άλυτη με ακρίβεια 1e-7 Σε έναν ιδανικό κόσμο, οι περιορισμοί δεν θα επέτρεπαν τέτοιες περιπτώσεις και εξακολουθούν να απαιτούν υψηλή ακρίβεια, έτσι ώστε να μην είναι εύκολο να λυθεί το πρόβλημα μέσω κάποιας γενικής αριθμητικής βελτιστοποίησης.)
Περιορισμοί
— Το x θα έχει μεταξύ 3 και 50 στοιχεία, συμπεριλαμβανομένων.
— Το y θα έχει τον ίδιο αριθμό στοιχείων με το x.
— Όλες οι συντεταγμένες θα είναι μεταξύ 0 και 10,000, συμπεριλαμβανομένων.
— τα x και y θα περιγράψουν ένα κυρτό πολύγωνο με αριστερόστροφη σειρά.
παραδείγματα
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Επιστροφές:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Ένα συμμετρικό αλλά ακανόνιστο εξάγωνο. Το παράδειγμα απάντησης αντιστοιχεί στο να το κόψετε στη μέση οριζόντια και να κάνετε δύο άλλες τομές στο κέντρο που χωρίζουν κάθε κομμάτι σε τρία μέρη.
1)
{0, 1000, 0}
{0, 0, 1000}
Επιστροφές:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Ορθογώνιο τρίγωνο. Και πάλι, μπορούμε να ξεκινήσουμε με μία από τις τρεις τομές κατά μήκος του άξονα συμμετρίας.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Επιστροφές:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Ακανόνιστο πεντάγωνο.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Επιστροφές: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Ένα τετράγωνο περιστρεφόταν 45 μοίρες.
[]
Μόνο εγγεγραμμένοι χρήστες μπορούν να συμμετάσχουν στην έρευνα. , Σας παρακαλούμε.
Έλυσα το πρόβλημα για
-
σε λιγότερο από 10 λεπτά
-
10-30 λεπτά
-
30-60 λεπτά
-
1-2 ώρες
-
σε περισσότερες από 2 ώρες
-
άλλος
Ψήφισαν 42 χρήστες. 47 χρήστες απείχαν.
Πηγή: www.habr.com