149. 直线上最多的点数-并查集做法

给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。

示例 1：

输入：points = [[1,1],[2,2],[3,3]]
输出：3

示例 2：

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

博主也是第一次用并查集这个方法，觉得确实很神奇，这个方法应该可以解决很多很难解决的问题，但是使用起来需要我们多做一些应用：

解题代码如下：

int find(int x,int *p){
    
    while(x!=p[x]){
    
        x=p[x];
    }
    return x;
}



int maxPoints(int** points, int pointsSize, int* pointsColSize){
    
    int p[pointsSize];
    int i,j;
    int max=0;
    int cei[pointsSize][2];
    for(i=0;i<pointsSize;i++){
    
        printf("||");
      
        int  cur=0;
        for(j=i+1;j<pointsSize;j++){
    
             
            cei[cur][0]=points[i][0]-points[j][0];
             cei[cur][1]=points[i][1]-points[j][1];
            cur++;

        }
  // printf("cur %d |",cur);
        int hash[pointsSize];
           for(j=0;j<cur;j++){
    
     
                   p[j]=j;
            }

        

        for(j=0;j<cur;j++){
    

            hash[j]=0;

            for(int k=j+1;k<cur;k++){
    
                if(cei[k][0]*cei[j][1]-cei[k][1]*cei[j][0]==0){
    
                    
                    p[k]=j;

                }
            }
        }
         for(j=0;j<cur;j++){
    
           
             max=fmax(max,++hash[find(j,p)]);
           // printf("%d %d |",find(j,p),hash[find(j,p)]);
         }



    }
    printf("max %d ",max);
    return max+1;
}