💯 🎚️ 👨🏿‍💻 टॉपकोडर ओपन 2019 के साथ चुनौती: केक को छह भागों में काटें 👨‍👨‍👧‍👧 ⚙️ 👩🏾‍🎨

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

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

समस्या का बयान

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

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

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

एक बिंदु के माध्यम से सीधी रेखाओं में तीन कटौती प्राप्त करें जो केक को छह समान आकार के टुकड़ों में विभाजित करेगा। प्रिंट {एक्स, वाई, डी 1, डी 2, डी 3}, जहां (एक्स, वाई) सभी तीन वर्गों का सामान्य बिंदु है, और डी 1, डी 2, डी 3 रेडियन में वर्गों की दिशा के कोण हैं।

परिभाषा

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

नोट

एक्स अक्ष के साथ सकारात्मक दिशा 0 (रेडियन) है, वाई अक्ष के साथ सकारात्मक दिशा पी / 2 (रेडियन) है।
दिशा d में कटौती किसी पूर्णांक k के लिए दिशा pi * k + d में कटौती के समान है।
आप किसी भी दिशा में आउटपुट कर सकते हैं, उन्हें [0, pi) से नहीं होना चाहिए।
डबल्स में केक आपके छह टुकड़ों के क्षेत्र की गणना करेगा। उत्तर स्वीकार किया जाएगा यदि उनके बीच सापेक्ष या पूर्ण अंतर 10 ^ (- 4) से कम है।
अधिक सटीक रूप से, X और Y, ग्रेडर द्वारा गणना किए जाने वाले आपके छह क्षेत्रों में सबसे छोटे और सबसे बड़े हैं। तब आपका उत्तर स्वीकार किया जाएगा यदि Y <max (X + 10 ^ (- 4), X * 1 + 10 ^ (- 4)))।
(समस्या के मूल संस्करण में, 1e-4 के बजाय सटीकता 1e-7 का उपयोग किया गया था। संग्रह में इस समस्या को हल करने के लिए, कॉल मामलों की उपस्थिति के कारण सटीकता की सीमा को कम कर दिया गया था, जो कि सटीकता के साथ कार्य को 1e-7 के साथ कार्य करने योग्य नहीं बनाता है। एक आदर्श दुनिया में, प्रतिबंध। ऐसे मामलों की अनुमति न दें और फिर भी उच्च सटीकता की आवश्यकता होती है, इसलिए कुछ सामान्य संख्यात्मक अनुकूलन के साथ समस्या को हल करना आसान नहीं है।)

प्रतिबंध

x में 3 से 50 तत्व शामिल हैं।
y में x जितने तत्व हैं।
सभी निर्देशांक 0 और 10,000 के बीच सम्मिलित हैं
x और y एक वामावर्त दिशा में उत्तल बहुभुज को परिभाषित करते हैं।

मूल अंग्रेजी में

समस्या कथन

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

आपके पास केक है। ऊपर से देखा, केक एक (सख्ती से) उत्तल बहुभुज है। आपको int [] sx और y में इसके कोने के निर्देशांक दिए गए हैं।

आपके पाँच मित्र हैं। अब आप केक को बराबर क्षेत्र के छह टुकड़ों में काटना चाहते हैं (लेकिन आवश्यक रूप से समान आकार नहीं)। बेशक, कोई भी पांच कट्स में ऐसा कर सकता है - लेकिन केवल एक सच्चा समर्थक इसे तीन में कर सकता है!

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

परिभाषा

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

नोट्स
- एक्स अक्ष के साथ सकारात्मक दिशा 0 (रेडियन) है, वाई अक्ष के साथ सकारात्मक दिशा पीआई / 2 (रेडियन) है।
- दिशा d में कटौती किसी पूर्णांक k के लिए दिशा pi * k + d में कटौती के समान है।
- आप किसी भी दिशा में लौट सकते हैं, उन्हें [0, पीआई] से नहीं होना चाहिए।
- यह डबल्स में आपके छह केक के टुकड़ों की गणना करेगा। उत्तर स्वीकार किया जाएगा यदि उनके बीच सापेक्ष या पूर्ण अंतर 10 ^ (- 4) से कम है।
- अधिक सटीक रूप से, एक्स और वाई को अपने छह क्षेत्रों में सबसे छोटा और सबसे बड़ा होने दें, जैसा कि ग्रेडर द्वारा गणना की जाती है। तब, आपका उत्तर स्वीकार किया जाएगा यदि Y <max (X + 10 ^ (- 4), X * (1 + 10 ^ (- 4)))।
- (समस्या का मूल संस्करण 1e-4 के बजाय 1e-7 परिशुद्धता का उपयोग करता है। संग्रह में इस समस्या को हल करने के लिए चुनौती के मामलों की मौजूदगी के कारण सटीक सीमा को कम कर दिया गया था, जो संभवतः 1e-7 परिशुद्धता के साथ कार्य को अनसुना कर देता है। एक आदर्श दुनिया में बाधाओं को ऐसे मामलों की अनुमति नहीं दी जाएगी और अभी भी उच्च परिशुद्धता की आवश्यकता होगी, ताकि कुछ सामान्य संख्यात्मक अनुकूलन के माध्यम से समस्या को हल करना आसान न हो।)

प्रतिबन्ध
- x में 3 और 50 तत्व शामिल होंगे।
- y में x के समान तत्व होंगे।
- सभी निर्देशांक 0 और 10,000 के बीच होंगे, समावेशी।
- x और y वामावर्त क्रम में एक उत्तल बहुभुज का वर्णन करेंगे।

उदाहरण

0)

{, 20, 30, 50, 30, 20}
{१०, ०, ०, १०, २०, २०}
यह दिखाता है:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787}

सममित लेकिन नियमित षट्भुज नहीं। उत्तर का एक उदाहरण इसे आधा क्षैतिज रूप से काटने और केंद्र में दो अन्य कटौती करने से मेल खाता है, जो प्रत्येक भाग को तीन भागों में विभाजित करता है।

1)

{0, 1000, 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 डिग्री घुमाया गया।

[ स्रोत ]

टॉपकोडर ओपन 2019 के साथ चुनौती: केक को छह भागों में काटें

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

समस्या कथन

उदाहरण

More articles: