Salve a tutti, qualcuno è in grado di scrivere un programma in Java che risolva il seguente problema?
Sia dato un file input.csv contenente un elenco di punti distinti su un piano, rappresentati tramite le loro coordinate (x,y). Le coordinate non sono necessariamente intere. Per nessuna tripla di tali punti passa una retta. Si chiede di generare un file output.csv con il sottoinsieme di tali punti che giacciono sulla frontiera dell'inviluppo convesso, usando l'algoritmo descritto sotto. Tali punti devono essere elencati nel file di output seguendo lo stesso ordine usato nel file di input.
Ecco l'algoritmo:
Si sceglie come punto "pivot" il punto con coordinata y minore (e in caso di parità, con coordinata x minore). Si ordinano gli altri punti in funzione dell'angolo tra la retta punto-pivot e l'asse x. Si "cammina" quindi sui punti ordinati in tal modo, partendo dal pivot e poi proseguendo dal punto 1. Ad ogni punto sul cammino si controlla se si sta "svoltando a sinistra" o "a destra". Una svolta "a destra" in un punto rivela che il punto non fa parte della frontiera dell'inviluppo convesso. Si scartano quindi questi punti in modo che il cammino costruito includa solo svolte "a sinistra".
