欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

给定二维平面上的n个点,找出位于同一直线上的点的最大数目

程序员文章站 2022-04-01 18:41:34
...

给定二维平面上的n个点,找出位于同一直线上的点的最大数目
/**

  • 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) {
    if(points.length <= 2) return points.length;
    int max = 2;
    int n = points.length;
    int x1, y1, x2, y2;
    int k = 1;//相同斜率的点
    int t = 0;//相同位置的点
    int i, j, m;
    for(i = 0; i < n; i++){
    k = 1;
    t = 0;
    for(j = i + 1; j < n; j++){
    x1 = points[i].x - points[j].x;
    y1 = points[i].y - points[j].y;
    if(x1 == 0 && y1 == 0) t++;
    else {
    k++;
    for(m = j + 1; m < n; m++){
    x2 = points[i].x - points[m].x;
    y2 = points[i].y - points[m].y;
    if(x1 * y2 == x2 * y1)k++;
    }
    }
    if(k + t > max)max = k + t;
    k = 1;
    }
    }
    return max;
    }
    }