Biorąc pod uwagę n punktów na płaszczyźnie 2D, znajdź maksymalną liczbę punktów, które leżą na tej samej linii prostej
Poniżej znajduje się rozwiązanie, które próbuję wdrożyć
/**
* 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;j<points.length;j++){
if((points[i].x!=points[j].x)||(points[i].y!=points[j].y)){
int coll=get_collinear(points[i].x,points[i].y,points[j].x,points[j].y,points);
if(coll>max)
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;
}
}
Działa w O (n ^ 3). W zasadzie wykonuję dwie pętle, porównując różne punkty na płaszczyźnie 2d. A następnie biorąc 2 punkty wysyłam te 2 punkty do metody get_collinear, która uderza w linię utworzoną przez te 2 punkty ze wszystkimi elementami tablicy, aby sprawdzić, czy 3 punkty są współliniowe. Wiem, że to metoda brutalnej siły. Jednak w przypadku, gdy dane wejściowe to [(0,0), (0,0)] mój wynik nie powiedzie się. Pętla else jest miejscem, w którym muszę dodać warunek, aby znaleźć takie przypadki. Czy ktoś może mi pomóc w rozwiązaniu tego. Czy istnieje lepsze rozwiązanie tego problemu w lepszym czasie działania. Nie mogę wymyślić żadnego.