TopCoder Open 2019 आव्हान: पाईचे सहा तुकडे करा

पदोपदीं "आमचे जिंकले: टॉपकोडर ओपन 2019" मी अल्गोरिदम ट्रॅकवरून समस्या प्रकाशित करतो (शास्त्रीय क्रीडा प्रोग्रामिंग. दीड तासात तुम्हाला Java, C#, C++ किंवा Python मधील तीन समस्या सोडवाव्या लागतील.)

1. सहा साठी पाई

समस्येची निर्मिती

वेळ मर्यादा 4 सेकंद आहे.

तुमच्याकडे पाई आहे. वरून पाहिल्यावर, केकचा आकार (कठोरपणे) बहिर्वक्र बहुभुजाचा असतो. तुम्हाला X आणि Y पूर्णांकांमध्ये शिरोबिंदूंचे निर्देशांक दिले आहेत.

तुमचे पाच मित्र आहेत. तुम्हाला पाई समान क्षेत्राच्या सहा तुकड्यांमध्ये विभाजित करायची आहे (परंतु समान आकार आवश्यक नाही). अर्थात, कोणीही ते पाच कटमध्ये करू शकतो, परंतु केवळ एक प्रो तीन कटमध्ये करू शकतो.

एका बिंदूमधून तीन सरळ रेषेतील कट शोधा जे पाईला सहा समान भागांमध्ये विभाजित करेल. मुद्रित करा {x, y, d1, d2, d3}, जेथे (x, y) तीनही कटांचा सामान्य बिंदू आहे आणि d1, d2, d3 हे रेडियनमधील कटांचे दिशा कोन आहेत.

व्याख्यावर्ग: CakeForSix
कृती: कापून घ्या
पॅरामीटर्स: int[], int[] रिटर्न: दुहेरी[] पद्धत स्वाक्षरी: दुहेरी[] कट(इंट[] x, इंट[] 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 हे त्रिज्यामध्ये त्यांच्या दिशा आहेत.

व्याख्या

वर्ग: CakeForSix
कृती: कापून घ्या
पॅरामीटर्स: int[], int[] रिटर्न: दुहेरी[] पद्धत स्वाक्षरी: दुहेरी[] कट(इंट[] x, इंट[] 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