Changamoto ya TopCoder Open 2019: kata mkate katika vipande sita

Kwenye njia "Yetu alishinda: TopCoder Open 2019" Ninachapisha matatizo kutoka kwa wimbo wa Algorithm (programu za kawaida za michezo. Katika saa moja na nusu unahitaji kutatua matatizo matatu katika Java, C#, C++ au Python.)

1. Pie kwa sita

Taarifa ya tatizo

Kikomo cha muda ni sekunde 4.

Una mkate. Inapotazamwa kutoka juu, keki ina umbo la poligoni mbonyeo (madhubuti). Unapewa kuratibu za wima katika nambari kamili za X na Y.

Una marafiki watano. Unataka kugawanya pai katika vipande sita vya eneo sawa (lakini si lazima sura sawa). Bila shaka, mtu yeyote anaweza kuifanya kwa kupunguzwa tano, lakini tu mtaalamu anaweza kufanya hivyo kwa kupunguzwa tatu.

Pata kupunguzwa kwa mstari wa tatu kwa njia moja ambayo itagawanya pie katika sehemu sita sawa. Chapisha {x, y, d1, d2, d3}, ambapo (x, y) ni sehemu ya kawaida ya mikato yote mitatu, na d1, d2, d3 ni pembe za mwelekeo wa kupunguzwa kwa radiani.

UfafanuziDarasa: CakeForSix
Mbinu: kata
Vigezo: int[], int[] Returns: double[] Mbinu sahihi: double[] kata(int[] x, int[] y)
(hakikisha njia yako ni ya umma)

maelezo

• Mwelekeo chanya kando ya mhimili wa x ni 0 (radians), mwelekeo chanya kando ya mhimili wa y ni pi/2 (radians).
• Kata katika mwelekeo wa d ni sawa na kata katika mwelekeo wa pi*k+d kwa nambari yoyote k.
• Unaweza kutoa mwelekeo wowote, sio lazima ziwe kutoka [0, pi).
• Mpangaji atahesabu eneo la vipande vyako sita vya keki kwa mara mbili. Jibu litakubaliwa ikiwa tofauti ya jamaa au kamili kati yao ni chini ya 10 ^(-4).
• Kwa usahihi zaidi, acha X na Y ziwe ndogo na kubwa zaidi kati ya maeneo yako sita yanayokokotwa na greda. Kisha jibu lako litakubaliwa ikiwa Y
• (Toleo la asili la tatizo lilitumia usahihi wa 1e-7 badala ya 1e-4. Ili kutatua tatizo hili kwenye kumbukumbu, kikomo cha usahihi kilipunguzwa kwa sababu ya kuwepo kwa kesi za kupiga simu ambazo zingeweza kufanya tatizo kutatuliwa kwa usahihi. ya 1e-7. Katika ulimwengu bora, mipaka hairuhusu kesi kama hizo na bado zinahitaji usahihi wa juu, kwa hivyo kusuluhisha shida na uboreshaji wa nambari kwa ujumla sio rahisi.)

Vikwazo

• x ina kutoka vipengele 3 hadi 50 pamoja.
• y ina idadi sawa ya vipengele kama x.
• kuratibu zote kati ya 0 na 10 zikiwa zimejumuishwa
• x na y hufafanua poligoni mbonyeo katika mwelekeo wa kinyume cha saa.

asili kwa Kiingereza

Taarifa ya Tatizo

Kikomo cha muda ni sekunde 4.

Una keki. Ikionekana kutoka juu, keki ni (madhubuti) ya poligoni iliyobonyea. Unapewa kuratibu za wima zake katika int[]sx na y.

Una marafiki watano. Sasa unataka kukata keki katika vipande sita vya eneo sawa (lakini si lazima sura sawa). Bila shaka, mtu yeyote anaweza kufanya hivyo kwa njia tano - lakini mtaalamu wa kweli pekee ndiye anayeweza kufanya hivyo katika tatu!

Tafuta vipande vitatu vya mstari wa moja kwa moja ukipitia sehemu moja ambayo hukata keki katika sehemu sita kubwa sawa. Rudisha {x, y, d1, d2, d3}, ambapo (x, y) ni sehemu ya kawaida ya miketo mitatu, na d1, d2, d3 ni maelekezo yao katika radiani.

Ufafanuzi

Darasa: CakeForSix
Mbinu: kata
Vigezo: int[], int[] Returns: double[] Mbinu sahihi: double[] kata(int[] x, int[] y)
(hakikisha njia yako ni ya umma)

Vidokezo
— Mwelekeo chanya kwenye mhimili wa x ni 0 (radians), mwelekeo chanya kwenye mhimili y ni pi/2 (radians).
— Kata katika mwelekeo d ni sawa na kata katika mwelekeo pi*k+d kwa nambari k yoyote.
- Unaweza kurudisha maelekezo yoyote, sio lazima yatoke [0,pi).
- Mtayarishaji wa darasa atahesabu maeneo ya vipande vyako sita vya keki kwa mara mbili. Jibu litakubaliwa ikiwa tofauti ya jamaa au kamili kati yao ni chini ya 10 ^(-4).
- Kwa usahihi zaidi, acha X na Y ziwe ndogo na kubwa zaidi kati ya maeneo yako sita, kama inavyokokotolewa na greda. Kisha, jibu lako litakubaliwa ikiwa Y < max( X + 10^(-4), X * (1+10^(-4)) ).
- (Toleo la asili la tatizo lilitumia usahihi wa 1e-7 badala ya 1e-4. Ili kutatua tatizo hili kwenye kumbukumbu kikomo cha usahihi kilipunguzwa kutokana na kuwepo kwa kesi za changamoto ambazo kuna uwezekano mkubwa wa kufanya kazi kutotatuliwa kwa usahihi wa 1e-7 Katika ulimwengu mzuri vikwazo havingeruhusu kesi kama hizi na bado zinahitaji usahihi wa juu, ili sio rahisi kutatua shida kupitia uboreshaji wa nambari za jumla.)

vikwazo
- x itakuwa na vitu kati ya 3 na 50, zikijumuishwa.
- y itakuwa na idadi ya vipengele sawa na x.
- Viwianishi vyote vitakuwa kati ya 0 na 10,000, zikijumuishwa.
- x na y itaelezea poligoni mbonyeo kwa mpangilio wa kinyume.

mifano

0)

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Returns:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

Heksagoni yenye ulinganifu lakini isiyo ya kawaida. Jibu la mfano linalingana na kuikata kwa nusu mlalo na kutengeneza sehemu nyingine mbili katikati ambayo hugawanya kila kipande katika vipande vitatu.

1)

{0, 1000, 0}
{0, 0, 1000}
Returns:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

Pembetatu ya kulia. Tena, tunaweza kuanza na moja ya mikato mitatu kwenye mhimili wa ulinganifu.

2)

{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Returns:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

Pentagon isiyo ya kawaida.

3)

{300, 400, 300, 200}
{500, 600, 700, 600}
Urejeshaji: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }

Mraba ilizunguka digrii 45.

[Chanzo]

Watumiaji waliojiandikisha pekee ndio wanaweza kushiriki katika utafiti. Weka sahihitafadhali.

Nilitatua tatizo kwa

• chini ya dakika 10

• Dakika 10 30-

• Dakika 30 60-

• Masaa 1-2

• kwa zaidi ya masaa 2

• nyingine

Watumiaji 42 walipiga kura. Watumiaji 47 walijizuia.

Chanzo: mapenzi.com