Sulle tracce pubblico problemi dal track 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
Il limite di tempo è di 4 secondi.
Hai una torta. Se guardi dall'alto, la torta ha la forma di un poligono (strictly) convesso. Ti sono date le coordinate dei vertici in numeri interi X e Y.
Hai cinque amici. Vuoi dividere la torta in sei parti di uguale area (ma non necessariamente della stessa forma). Certo, chiunque può farlo con cinque tagli, ma solo un esperto può farlo con tre tagli.
Trova tre tagli lineari che passano per un punto, che dividano 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, mentre 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 è equivalente a un taglio nella direzione pi*k+d per qualsiasi numero intero k.
- Puoi restituire qualsiasi direzione, non devono necessariamente essere tra [0, pi).
- Il valutatore calcolerà le aree dei tuoi sei pezzi di torta in double. La risposta sarà accettata se la differenza relativa o assoluta tra di esse è inferiore a 10^(-4).
- Più precisamente, sia X e Y le aree più piccola e più grande tra le tue sei aree calcolate dal valutatore. Allora la tua risposta sarà accettata se Y <max (X+10^(-4), X*1+10^(-4))).
- (Nella versione originale del problema è stata utilizzata una precisione di 1e-7 invece di 1e-4. Per risolvere questo problema, nel database il limite di precisione è stato abbassato a causa di casi di chiamata che probabilmente rendono il problema non risolvibile con una precisione di 1e-7. In un mondo ideale, le limitazioni non dovrebbero permettere tali casi e richiedere comunque alta precisione, quindi risolvere il problema utilizzando una certa ottimizzazione numerica generale non è facile.)
Limitazioni
- x contiene da 3 a 50 elementi inclusi.
- y contiene lo stesso numero di elementi che x.
- tutte le coordinate tra 0 e 10 000 inclusi
- x e y definiscono un poligono convesso in senso antiorario.
Originale in inglese
Descrizione del problema
Il limite di tempo è di 4 secondi.
Hai una torta. Vista dall'alto, la torta è un poligono (strettamente) convesso. Ti sono date le coordinate dei suoi vertici negli int[] x e y.
Hai cinque amici. Ora vuoi tagliare la torta in sei pezzi di area uguale (ma non necessariamente di forma uguale). Naturalmente, chiunque può farlo con cinque tagli — ma solo un vero professionista può farlo in tre!
Trova tre tagli rettilinei che passano per lo stesso punto e che tagliano la torta in sei parti ugualmente grandi. 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 necessariamente essere comprese in [0,pi).
— Il valutatore calcolerà le aree dei tuoi sei pezzi di torta in numeri floating-point. La risposta sarà accettata se la differenza relativa o assoluta tra di essi è inferiore a 10^(-4).
— Più precisamente, siano X e Y 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 l'upsovling di questo problema nell'archivio, il limite di precisione è stato abbassato a causa dell'esistenza di casi di sfida che molto probabilmente rendono il compito irrisolvibile con una precisione di 1e-7. In un mondo ideale, i vincoli non permetterebbero tali casi e richiederebbero comunque un'alta precisione, in modo che non sia 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 comprese tra 0 e 10.000, inclusi.
— x e y descriveranno un poligono convesso in ordine antiorario.
Esempi
0)
{0, 20, 30, 50, 30, 20}
{10, 0, 0, 10, 20, 20}
Restituisce:
{24.999999999437453, 9.999999999500002, 0.0, 0.7266423406817211, 2.4149503129080787 }
Un esagono simmetrico, ma non regolare. Un esempio di risposta corrisponde a tagliarlo a metà in orizzontale ed effettuare altri due tagli al centro, che dividono ciascuna parte in tre parti.
1)
{0, 1000, 0}
{0, 0, 1000}
Restituisce:
{333.3333333331763, 333.3333333332546, 0.7853981633986264, 2.0344439357948154, 2.6779450445891753 }
Un triangolo rettangolo. Anche in questo caso, possiamo iniziare con uno dei tre tagli lungo l'asse di simmetria.
2)
{40, 70, 90, 90, 50}
{30, 20, 40, 100, 60}
Restituisce:
{69.79517771922892, 52.77575974637605, 2.0616329654335885, 3.637826104091601, 4.32123485812475 }
Un pentagono irregolare.
3)
{300, 400, 300, 200}
{500, 600, 700, 600}
Restituisce: {299.99999999974995, 599.9999999995, 0.0, 1.107148717794088, 2.034443935795705 }
Un quadrato ruotato di 45 gradi.
[]
Solo gli utenti registrati possono partecipare al sondaggio. , per favore.
Ho risolto il problema in
meno di 10 minuti
10-30 minuti
30-60 minuti
1-2 ore
più di 2 ore
altro
Hanno votato 42 utenti. Si sono astenuti 47 utenti.
Fonte: habr.com
