Dati i n punti su un piano 2D, trova il numero massimo di punti che si trovano sulla stessa linea retta

Di seguito è la soluzione che sto cercando di implementare

/** * Definition for a point. * class Point { * int x; * int y; * Point() { x = 0; y = 0; } * Point(int a, int b) { x = a; y = b; } * } */ public class Solution { public int maxPoints(Point[] points) { int max=0; if(points.length==1) return 1; for(int i=0;i<points.length;i++){ for(int j=0;jmax) max=coll; } else{ **Case where I am suffering** } } } return max; } public int get_collinear(int x1,int y1,int x2, int y2,Point[] points) { int c=0; for(int i=0;i<points.length;i++){ int k1=x1-points[i].x; int l1=y1-points[i].y; int k2=x2-points[i].x; int l2=y2-points[i].y; if((k1*l2-k2*l1)==0) c++; } return c; } } 

Funziona a O (n ^ 3). Quello che sto fondamentalmente facendo è eseguire due loop confrontando vari punti nel piano 2D. E poi prendendo 2 punti invio questi 2 punti al metodo get_collinear che colpisce la linea formata da questi 2 punti con tutti gli elementi dell’array per verificare se i 3 punti sono collineari. So che questo è un metodo di forza bruta. Tuttavia, nel caso in cui l’input sia [(0,0), (0,0)] il mio risultato non riesce. Il ciclo alternativo è dove devo aggiungere una condizione per capire questi casi. Qualcuno può aiutarmi con la soluzione a questo. E esiste una soluzione migliore a questo problema in tempi di esecuzione migliori. Non riesco a pensare a nessuno.