🥇Problema del TopCoder Open 2019: tagliamo la torta in sei parti

Compito del TopCoder Open 2019: tagliare una torta in sei parti
Sulle tracce «I nostri hanno vinto: TopCoder Open 2019» pubblico i problemi della traccia Algorithm (programmazione competitiva classica. In un'ora e mezza bisogna risolvere tre problemi in Java, C#, C++ o Python.)

1. Torta per sei

Definizione del compito

Limite di tempo — 4 secondi.

Hai una torta. Vista dall'alto, la torta ha la forma di un poligono convesso (strictly). Ti sono date le coordinate dei vertici in numeri interi X e Y.

Hai cinque amici. Vuoi suddividere la torta in sei parti di area uguale (ma non necessariamente della stessa forma). Naturalmente, chiunque può farlo con cinque tagli, ma solo un professionista può farlo con tre tagli.

Trova tre tagli retti che passano per un punto, che divideranno la torta in sei parti di uguale area. Restituisci {x, y, d1, d2, d3}, dove (x, y) è il punto comune di tutti e tre i tagli, e d1, d2, d3 sono gli angoli di direzione dei tagli in radianti.

DefinizioneClasse: CakeForSix
Metodo: cut
Parametri: int[], int[]
Restituisce: double[]
Firma del metodo: double[] cut(int[] x, int[] y)
(assicurati che il tuo metodo sia pubblico)

Note

La direzione positiva lungo l'asse x è 0 (radianti), la direzione positiva lungo l'asse y è pi/2 (radianti).
Un taglio nella direzione d è analogo a un taglio nella direzione pi*k+d per qualsiasi numero intero k.
Puoi fornire qualsiasi direzione, non è necessario che siano tra [0, pi).
Il valutatore calcolerà le aree dei sei pezzi di torta in doubles. La risposta sarà accettata se la differenza relativa o assoluta tra di esse è inferiore a 10^(-4).
In particolare, siano X e Y le aree più piccola e più grande tra le sei aree calcolate dal valutatore. La tua risposta sarà accettata se Y < max (X+10^(-4), X*1+10^(-4)).
(Nella versione originale del problema veniva utilizzata una precisione di 1e-7 invece di 1e-4. Per risolvere questo problema, il limite di precisione è stato abbassato a causa della presenza di casi di chiamata che probabilmente renderebbero il problema irrisolvibile con una precisione di 1e-7. In un mondo ideale, le restrizioni non consentirebbero tali casi e richiederebbero comunque alta precisione, quindi risolvere il problema mediante alcune ottimizzazioni numeriche generali non è semplice.)

Limitazioni

x contiene da 3 a 50 elementi inclusi.
y contiene lo stesso numero di elementi di x.
tutte le coordinate tra 0 e 10.000 inclusi
x e y definiscono un poligono convesso in senso antiorario.

Original in English

Problema

Il limite di tempo è di 4 secondi.

Hai una torta. Vista dall'alto, la torta è un poligono (strettamente) convesso. Ti vengono forniti le coordinate dei suoi vertici negli array int[] x e y.

Hai cinque amici. Ora vuoi tagliare la torta in sei pezzi di area uguale (ma non necessariamente di forma uguale). Ovviamente, chiunque può farlo in cinque tagli — ma solo un vero professionista può farlo in tre!

Trova tre tagli in linea retta che passano attraverso lo stesso punto e che dividono la torta in sei parti di uguale grandezza. Restituisci {x, y, d1, d2, d3}, dove (x, y) è il punto comune dei tre tagli e d1, d2, d3 sono le loro direzioni in radianti.

Definizione

Classe: CakeForSix
Metodo: cut
Parametri: int[], int[]
Restituisce: double[]
Firma del metodo: double[] cut(int[] x, int[] y)
(assicurati che il tuo metodo sia pubblico)

Note
— La direzione positiva lungo l'asse x è 0 (radianti), la direzione positiva lungo l'asse y è pi/2 (radianti).
— Un taglio nella direzione d è lo stesso di un taglio nella direzione pi*k+d per qualsiasi intero k.
— Puoi restituire qualsiasi direzione, non devono essere da [0,pi).
— Il valutatore calcolerà le aree dei tuoi sei pezzi di torta in numeri decimali. La risposta sarà accettata se la differenza relativa o assoluta tra di loro è inferiore a 10^(-4).
— Più precisamente, poniamo che X e Y siano il più piccolo e il più grande dei tuoi sei aree, come calcolato dal valutatore. La tua risposta sarà accettata se Y < max(X + 10^(-4), X * (1 + 10^(-4))).
— (La versione originale del problema utilizzava una precisione di 1e-7 invece di 1e-4. Per risolvere questo problema nell'archivio, il limite di precisione è stato abbassato a causa dell'esistenza di casi di sfida che rendono molto probabilmente irrisolvibile il compito con una precisione di 1e-7. In un mondo ideale, i vincoli non permetterebbero tali casi e richiederebbero ancora alta precisione, così da non rendere facile risolvere il problema tramite qualche ottimizzazione numerica generale.)

Vincoli
— x avrà tra 3 e 50 elementi, inclusi.
— y avrà lo stesso numero di elementi di x.
— Tutte le coordinate saranno tra 0 e 10.000, inclusi.
— x e y descriveranno un poligono convesso in ordine antiorario.

Esempi

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

Esagono simmetrico, ma non corretto. Un esempio di risposta corrisponde al taglio in due parti orizzontalmente e a due ulteriori tagli al centro, che dividono ciascuna parte in tre parti.

Compito del TopCoder Open 2019: tagliare una torta in sei parti

1)

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

Triangolo rettangolo. Anche in questo caso, possiamo iniziare con uno dei tre tagli lungo l'asse di simmetria.

Compito del TopCoder Open 2019: tagliare una torta in sei parti

2)

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

Pentagono irregolare.

Compito del TopCoder Open 2019: tagliare una torta in sei parti

3)