টপকোডার ওপেন 2019 চ্যালেঞ্জ: পাইটিকে ছয় টুকরো করুন

ট্রেইলে "আমাদের জিতেছে: TopCoder Open 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, পাই) থেকে হতে হবে না।
• গ্রেডার আপনার ছয় পিস কেকের ক্ষেত্রফল ডবলে গণনা করবে। তাদের মধ্যে আপেক্ষিক বা পরম পার্থক্য 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 (রেডিয়ান)।
— যে কোনো পূর্ণসংখ্যা k-এর জন্য d-এর দিকনির্দেশে কাটা 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