TopCoder Open 2019 გამოწვევა: გაჭერით ღვეზელი ექვს ნაწილად

კვალდაკვალ "ჩვენმა გაიმარჯვა: TopCoder Open 2019" მე ვაქვეყნებ პრობლემებს ალგორითმის ტრეკიდან (კლასიკური სპორტული პროგრამირება. საათნახევარში გჭირდებათ სამი პრობლემის გადაჭრა 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 იყოს ყველაზე პატარა და დიდი თქვენი ექვსი არედან, რომელიც გამოითვლება კლასერის მიერ. მაშინ თქვენი პასუხი მიიღება, თუ 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)
(დარწმუნდით, რომ თქვენი მეთოდი საჯაროა)

შენიშვნები
— x ღერძის გასწვრივ დადებითი მიმართულება არის 0 (რადიანი), დადებითი მიმართულება y ღერძის გასწვრივ არის pi/2 (რადიანი).
— დ მიმართულებით ჭრა იგივეა, რაც 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