Visualizzazione dei risultati da 1 a 3 su 3

Discussione: inviluppo convesso

  1. #1
    Utente di HTML.it
    Registrato dal
    Jun 2014
    Messaggi
    1

    inviluppo convesso

    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".

  2. #2
    Utente di HTML.it L'avatar di minomic
    Registrato dal
    Nov 2010
    Messaggi
    635
    Ciao,
    qui non si svolgono esercizi su richiesta e non si fornisce codice pronto.


  3. #3

    Moderazione

    Esatto. Rileggi il regolamento e ritenta, sarai più fortunato.
    Amaro C++, il gusto pieno dell'undefined behavior.

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2025 vBulletin Solutions, Inc. All rights reserved.