Արահետի վրա Ես հրապարակում եմ խնդիրները Ալգորիթմ ուղուց (դասական սպորտային ծրագրավորում: Մեկուկես ժամում պետք է երեք խնդիր լուծել 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 ուղղությամբ ցանկացած ամբողջ թվի կտրվածքին:
- Դուք կարող եք դուրս բերել ցանկացած ուղղություն, պարտադիր չէ, որ դրանք լինեն [0, pi-ից):
- Գրեյդերը կհաշվի ձեր վեց կտոր տորթի մակերեսը կրկնակի: Պատասխանը կընդունվի, եթե նրանց միջև հարաբերական կամ բացարձակ տարբերությունը փոքր է 10^(-4):
- Ավելի ճիշտ, թող X-ը և 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)
(համոզվեք, որ ձեր մեթոդը հրապարակային է)
Notes
— x առանցքի երկայնքով դրական ուղղությունը 0 է (ռադիաններ), y առանցքի երկայնքով դրական ուղղությունը՝ pi/2 (ռադիաններ):
— 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}
Վերադարձ.
Քառակուսին պտտվել է 45 աստիճանով։
[]
Հարցմանը կարող են մասնակցել միայն գրանցված օգտվողները։ , խնդրում եմ:
Ես լուծեցի խնդիրը
-
10 րոպեից պակաս ժամանակահատվածում
-
10-30 րոպե
-
30-60 րոպե
-
1-2 ժամ
-
ավելի քան 2 ժամում
-
այլ
Քվեարկել է 42 օգտատեր։ 47 օգտատեր ձեռնպահ է մնացել։
Source: www.habr.com