🥇TopCoder Open 2019 feladat: tortát vágunk hat részre

Feladat a TopCoder Open 2019-ből: tortát hat részre vágunk
Nyomozáson „Győztek a mieink: TopCoder Open 2019” publikálom a feladatokat az Algoritmus pályáról (hagyományos sportprogramozás. Másfél óra alatt három feladatot kell megoldani Java, C#, C++ vagy Python nyelven.)

1. Torta hat személyre

Lépjünk át a kitűzött feladatra: írjunk egy XDP mechanizmust SYN cookie-kkal.

Időkorlát — 4 másodperc.

Van egy tortája. Ha felülről nézi, a torta (szigorúan) konvex sokszög alakú. A csúcsok koordinátái egész számok.

Önnek öt barátja van. Szeretné a tortát hat egyenlő területű részre osztani (de nem feltétlenül azonos alakúra). Természetesen bárki meg tudja ezt tenni öt vágással, de csak a profik tudják megcsinálni három vágással.

Találjon három vágást egyetlen ponton át, amelyek a tortát hat egyenlő területű részre osztják. Adja meg {x, y, d1, d2, d3}, ahol (x, y) a három vágás közös pontja, míg d1, d2, d3 a vágások irányszögei radiánban.

DefinícióOsztály: CakeForSix
Metódus: cut
Paraméterek: int[], int[]
Visszatér: double[]
Metódus aláírása: double[] cut(int[] x, int[] y)
(győződjön meg arról, hogy a metódusa nyilvános)

Megjegyzések

A pozitív irány az x tengely mentén 0 (radián), a pozitív irány az y tengely mentén pi/2 (radián).
A vágás d irányba megegyezik a vágással pi*k+d irányban, bármely egész szám k esetén.
Bármilyen irányt megadhat, nem kell feltétlenül [0, pi) tartományban lennie.
A grader kiszámítja a torta hat szeletének területét doubles formátumban. A válasz akkor lesz elfogadva, ha a relatív vagy abszolút eltérés közöttük kevesebb, mint 10^(-4).
Pontosabban, legyen X és Y a legkisebb és legnagyobb a hat terület közül, amelyet a grader számított. Akkor a válasza elfogadva lesz, ha Y <max (X+10^(-4), X*1+10^(-4))).
(A feladat eredeti verziójában a pontosság 1e-7 volt a 1e-4 helyett. E probléma megoldásához az archívumban a pontosság határa csökkent, mivel voltak olyan esetek, amelyek valószínűleg lehetetlenné tették a feladat megoldását 1e-7 pontosággal. Ideális körülmények között a korlátok nem engedhetik meg az ilyen eseteket, és továbbra is magas pontosságot igényelnek, így a probléma megoldása nem egyszerű valamilyen általános numerikus optimalizációval.)

Korlátozások

x 3 és 50 közötti elemeket tartalmaz, beleértve.
y annyi elemet tartalmaz, mint x.
minden koordináta 0 és 10 000 között, beleértve
x és y egy konvex sokszöget határoznak meg, az óramutató járásával ellentétes irányban.

Eredeti angolul

Feladatmeghatározás

Időkorlát: 4 másodperc.

Van egy tortád. Felülről nézve a torta egy (szigorúan) konvex sokszög. Meg van adva a csúcsainak koordinátái az int[] x és y tömbökben.

Van öt barátod. Most azt szeretnéd, ha a tortát hat egyenlő területű (de nem feltétlenül egyforma formájú) darabra vágnád. Természetesen ezt öt vágással bárki megteheti — de csak egy igazi profi tudja megoldani három vágással!

Találj három egyenesen átvágott vágást, amely ugyanazon a ponton halad át, és a tortát hat egyenlő méretű részre vágja. Térj vissza {x, y, d1, d2, d3} értékkel, ahol (x, y) a három vágás közös pontja, és d1, d2, d3 irányai radiánban.

Definíció

Osztály: CakeForSix
Metódus: cut
Paraméterek: int[], int[]
Visszatér: double[]
Metódus aláírása: double[] cut(int[] x, int[] y)
(győződjön meg arról, hogy a metódusa nyilvános)

Megjegyzések
— A pozitív irány az x tengely mentén 0 (radián), a pozitív irány az y tengely mentén pi/2 (radián).
— A d irányú vágás ugyanaz, mint a pi*k+d irányú vágás minden egész k esetén.
— Bármilyen irányt visszaadhatsz, nem kell, hogy a [0,pi) intervallumban legyenek.
— A javító a hat tortatészta részed területeit lebegőpontos értékként számolja ki. A válasz elfogadott lesz, ha a különbség viszonylag vagy abszolút mértéke kevesebb mint 10^(-4).
— Pontosabban, legyen X és Y a legkisebb és a legnagyobb a hat területeid közül, ahogy a javító számolta. Akkor a válaszod elfogadott lesz, ha Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (A probléma eredeti verziója 1e-7 pontosságot használt 1e-4 helyett. A probléma archívumában való megoldásához az érzékenységi limitet csökkentették, mivel a létezésük miatt kihívási esetek valószínűleg megnehezítik a feladat megoldását 1e-7 pontossággal. Egy ideális világban a korlátok nem engednék meg ilyen eseteket, és mégis magas pontosságot követelnének, így nem lenne könnyű megoldani a problémát általános numerikus optimalizálással.)

Korlátozások
— az x tömb 3 és 50 közötti elemeket tartalmaz, beleértve.
— az y tömbnek ugyanannyi eleme van, mint az x tömbnek.
— Minden koordináta 0 és 10 000 között van, beleértve.
— az x és y tömbök egy konvex sokszöget írnak le az óramutató járásával ellentétes irányban.

Példák

{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Visszatérítendő:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }

Szimmetrikus, de nem szabályos hatszög. A válasz például a vízszintes középső átvágásról és a két másik középső vágásról szól, amelyek mindkét részt három részre osztják.

Feladat a TopCoder Open 2019-ből: tortát hat részre vágunk

1)

{0, 1000, 0}
{0, 0, 1000}
Visszatérítendő:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }

Derékszögű háromszög. Ismételten, kezdhetjük a három vágás egyikével a szimmetria tengelye mentén.

Feladat a TopCoder Open 2019-ből: tortát hat részre vágunk

2)

{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Visszatérítendő:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }

Rendetlen ötszög.

Feladat a TopCoder Open 2019-ből: tortát hat részre vágunk

3)