Ho intenzione di calcolare tutti i coefficienti angolari in complessità (✓N)*N (non so se sia scritta bene, ho seguito i constraint del problema) e poi li salvo in una mappa incrementandone il count ogni volta che trovo un coeffangolare già presente in essa. Infine trovo il massimo coefficiente scannerizzando l array di chiavi della mappa. Secondo voi si sta nei tl? Se no se qualcuno ha consigli, sono ben accetti 
.
Be’ in teoria non va trovato il coefficiente più frequente, visto che 4 vertici di un quadrato non sono collineari ma hanno stessi coefficienti angolari, dovresti salvarti per ogni punto quanti punti ha collineari con un dato coefficiente angolare.
1 Mi Piace
Vero hai ragione😂… ma comunque si riesce a stare nei TL Cosi?
Bella domanda, così a naso ti direi che non entra, dato che il TL è 0.25.
Comunque potresti spiegarmi meglio come sarebbe il tuo algoritmo per avere quella complessità?
Oddio, è un po’ incasinato, spero di riuscire a spiegarlo decentemente:
praticamente scorri tutto l’array dei punti come in una selection sort, eccetto che ti fermi quando arrivi a radice di N(seguendo i constraint del problema) per ogni iterazione del ciclo esterno calcoli i coefficienti angolari di ogni punto metti in una mappa quel certo coefficiente angolare e un array di punti corrispondenti. Poi estraggo il set dalla mappa e lo scorro, controllando a partire dagli array più lunghi di punti, quanti di essi sono collineari. Si può fare probabilmente in maniera più semplice io ho buttato un idea così , ma 0.25 di tl è davvero troppo basso…tu che l hai risolto che consiglio mi daresti?
Eh in effetti non ho capito , cioè cos’è il coefficiente angolare di un punto?
Comunque se vuoi una mano c’è un constraint non specificato nel problema e secondo me non troppo scontato, ossia che i punti hanno tutte le coordinate diverse (dato che se due stelle si sovrapponessero non sarebbero più distinguibili nel cielo), questo ti consente insieme alle altre limitazioni di rimanere con un set di coefficienti angolari possibili mooolto ridotto per N grandi
1 Mi Piace
Anche secondo me andrebbe specificato. Non ci avevo fatto caso, Grazie !
1 Mi Piace