ટોપકોડર ઓપન 2019 પડકાર: પાઇને છ ટુકડાઓમાં કાપો

પગેરું પર "અમારું જીત્યું: ટોપકોડર ઓપન 2019" હું અલ્ગોરિધમ ટ્રેકમાંથી સમસ્યાઓ પ્રકાશિત કરું છું (ક્લાસિકલ સ્પોર્ટ્સ પ્રોગ્રામિંગ. દોઢ કલાકમાં તમારે Java, C#, C++ અથવા Python માં ત્રણ સમસ્યાઓ હલ કરવાની જરૂર છે.)

1. છ માટે પાઇ

સમસ્યાની રચના

સમય મર્યાદા 4 સેકન્ડ છે.

તમારી પાસે પાઇ છે. જ્યારે ઉપરથી જોવામાં આવે છે, ત્યારે કેક (કડકથી) બહિર્મુખ બહુકોણનો આકાર ધરાવે છે. તમને X અને Y પૂર્ણાંકોમાં શિરોબિંદુઓના કોઓર્ડિનેટ્સ આપવામાં આવ્યા છે.

તમારા પાંચ મિત્રો છે. તમે પાઇને સમાન વિસ્તારના છ ટુકડાઓમાં વિભાજીત કરવા માંગો છો (પરંતુ તે જ આકાર જરૂરી નથી). અલબત્ત, કોઈ પણ તેને પાંચ કટમાં કરી શકે છે, પરંતુ માત્ર એક પ્રો જ તેને ત્રણ કટમાં કરી શકે છે.

એક બિંદુ દ્વારા ત્રણ સીધી રેખા કાપો જે પાઇને છ સમાન ભાગોમાં વિભાજિત કરશે. છાપો {x, y, d1, d2, d3}, જ્યાં (x, y) ત્રણેય કટનો સામાન્ય બિંદુ છે, અને d1, d2, d3 એ રેડિયનમાં કટના દિશા ખૂણા છે.

વ્યાખ્યાવર્ગ: CakeForSix
પદ્ધતિ: કાપો
પરિમાણો: int[], int[] વળતર: ડબલ[] પદ્ધતિ હસ્તાક્ષર: ડબલ[] કટ(int[] x, int[] 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[] વળતર: ડબલ[] પદ્ધતિ હસ્તાક્ષર: ડબલ[] કટ(int[] x, int[] 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