Ciao a tutti, sto praticamente impazzendo nel cercare di capire come risolvere il problema fontane.
Qualcuno di voi può darmi qualche dritta su come risolverlo?
Sapresti determinare la soluzione per un percorso rettilineo? Se sì, cosa cambia quando vengono inseriti i cambi di direzione?
Come indicato dal tag la soluzione necessita l’implementazione di una struttura di dato,
ma attualmente non mi viene in mente nessun modo per poter applicare le strutture che conosco (Segment Tree, Fenwick Tree).
Le strutture dati servono solo a velocizzare la soluzione, ma questa devi avercela già in mente no? 
L’unica strategia che mi viene in mente(non sono sicuro che sia corretta) è di iterare per ogni vertice
e mi salvo la massima distanza tra una fontana e la precedente meno 100
per ogni fontana tra il vertice e il successivo.
Prova a descrivere meglio l’algoritmo che hai in mente, in questo modo ti è più semplice capire se la soluzione è corretta e se la complessità è sufficiente 
Okay, provo a spiegartelo meglio.
Per prima cosa dichiaro tre variabili
A = posizione precedente(all’ inizio corrisponde al primo vertice)
B = la distanza tra l’ultima fontana vista e il vertice su cui itero
C = massima distanza tra due posizioni
Come detto prima itero per ogni vertice(tranne l’ultimo)
Per ogni fontana tra il vertice e il successivo
1) calcolo distanza(fontana, A) e gli aggiungo B
2) C = max(C, risultato calcolato in 1)
3) B = 0
4) A = fontana attuale
B = B + distanza(vertice successivo, A)
C = max(C, B)
A = vertice successivo
Alla fine del ciclo il risultato è uguale a C - 100
Ok, ma manca un piccolo particolare: come capisci quali sono le fontane tra due vertici successivi? E come fai a “percorrerle” nell’ordine giusto?
Per quanto riguarda il percorso rettilineo una fontana è tra due vertici successivi se la x della fontana è compresa tra le x dei vertici.
Salvo le fontane in un vector in ordine crescente in base alla x.
Perfetto, riesci ad adattare questa soluzione alla versione 2D? Ovvero quanto il circuito ha i cambi di direzione? Se sì come? E con che costo?
Finalmente 100/100 
Ho utilizzato un altro vector con le fontane ordinate in base alla y
e un segment tree per trovare la distanza maggiore tra due fontane.
1 Mi Piace
Volevo farti arrivare poco a poco ai Segment ma a quanto pare non è stato necessario.
Very good! 