टॉपकोडर ओपन 2019 चुनौती: पाई को छह टुकड़ों में काटें

बाद में "हमारी जीत हुई: टॉपकोडर ओपन 2019" मैं एल्गोरिथम ट्रैक से समस्याएं प्रकाशित करता हूं (शास्त्रीय खेल प्रोग्रामिंग। डेढ़ घंटे में आपको जावा, सी#, सी++ या पायथन में तीन समस्याओं को हल करना होगा।)

1. छह के लिए पाई

समस्या का निरूपण

समय सीमा 4 सेकंड है.

आपके पास एक पाई है. ऊपर से देखने पर, केक का आकार (सख्ती से) उत्तल बहुभुज जैसा होता है। आपको X और Y पूर्णांकों में शीर्षों के निर्देशांक दिए गए हैं।

आपके पांच दोस्त हैं. आप पाई को समान क्षेत्र के छह टुकड़ों में विभाजित करना चाहते हैं (लेकिन जरूरी नहीं कि आकार समान हो)। बेशक, कोई भी इसे पांच कट में कर सकता है, लेकिन केवल एक पेशेवर ही इसे तीन कट में कर सकता है।

एक बिंदु से होकर जाने वाली सीधी रेखाओं में तीन कट खोजें जो पाई को छह बराबर भागों में विभाजित करेंगे। {x, y, d1, d2, d3} प्रिंट करें, जहां (x, y) तीनों कटों का सामान्य बिंदु है, और d1, d2, d3 रेडियन में कट के दिशा कोण हैं।

परिभाषाकक्षा: केकफॉरसिक्स
विधि:काटो
पैरामीटर: int[], int[] रिटर्न: डबल[] विधि हस्ताक्षर: डबल[] कट(int[] x, int[] y)
(सुनिश्चित करें कि आपकी विधि सार्वजनिक है)

नोट्स

• x-अक्ष के अनुदिश सकारात्मक दिशा 0 (रेडियन) है, y-अक्ष के अनुदिश सकारात्मक दिशा pi/2 (रेडियन) है।
• d दिशा में कटौती किसी भी पूर्णांक k के लिए pi*k+d दिशा में कटौती के समान है।
• आप किसी भी दिशा को आउटपुट कर सकते हैं, उनका [0, pi) से होना आवश्यक नहीं है।
• ग्रेडर आपके केक के छह टुकड़ों के क्षेत्रफल की गणना दोगुने में करेगा। यदि उनके बीच सापेक्ष या पूर्ण अंतर 10^(-4) से कम है तो उत्तर स्वीकार किया जाएगा।
• अधिक सटीक रूप से, ग्रेडर द्वारा गणना किए गए आपके छह क्षेत्रों में से X और Y को सबसे छोटा और सबसे बड़ा होने दें। तब आपका उत्तर स्वीकार किया जायेगा यदि 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 रेडियन में उनकी दिशाएं हैं।

परिभाषा

कक्षा: केकफॉरसिक्स
विधि:काटो
पैरामीटर: int[], int[] रिटर्न: डबल[] विधि हस्ताक्षर: डबल[] कट(int[] x, int[] y)
(सुनिश्चित करें कि आपकी विधि सार्वजनिक है)

नोट्स
- x अक्ष के अनुदिश सकारात्मक दिशा 0 (रेडियन) है, y अक्ष के अनुदिश सकारात्मक दिशा pi/2 (रेडियन) है।
- दिशा d में कटौती किसी भी पूर्णांक k के लिए दिशा pi*k+d में कटौती के समान है।
- आप कोई भी दिशा-निर्देश लौटा सकते हैं, उनका [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