Dados n puntos en un plano 2D, encuentre el número máximo de puntos que se encuentran en la misma línea recta.
Análisis
Este problema se puede resolver contando puntos que tengan la misma pendiente para cada punto. Al contar, debemos tener cuidado con los puntos duplicados y los puntos en las líneas verticales.
Solución Java
public int maxPoints(Point[] points) { if(points == null || points.length == 0) return 0; HashMap<Double, Integer> result = new HashMap<Double, Integer>(); int max=0; for(int i=0; i<points.length; i++){ int duplicate = 1;// int vertical = 0; for(int j=i+1; j<points.length; j++){ //handle duplicates and vertical if(points[i].x == points[j].x){ if(points[i].y == points[j].y){ duplicate++; }else{ vertical++; } }else{ double slope = points[j].y == points[i].y ? 0.0 : (1.0 * (points[j].y - points[i].y)) / (points[j].x - points[i].x); if(result.get(slope) != null){ result.put(slope, result.get(slope) + 1); }else{ result.put(slope, 1); } } } for(Integer count: result.values()){ if(count+duplicate > max){ max = count+duplicate; } } max = Math.max(vertical + duplicate, max); result.clear(); } return max; } |
La relación entre casos normales, casos verticales y casos duplicados se puede mostrar de la siguiente manera:
