Max Points on a Line

来源：Leetcode

原帖：https://oj.leetcode.com/problems/max-points-on-a-line/

题目：
Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

代码：

 /**  
  * Definition for a point.  
  * struct Point {  
  *   int x;  
  *   int y;  
  *   Point() : x(0), y(0) {}  
  *   Point(int a, int b) : x(a), y(b) {}  
  * };  
  */  
   
 class Solution {  
 public:  
   // int GCD(int a, int b){  
   //   if(a == 0)   
   //     return b;  
   //   else   
   //     return GCD(a, b%a);  
   // }  
     
   struct hashfunc {   
     size_t operator() (const pair<int,int>& l) const {   
       return l.first ^ l.second;   
     }  
   };    
     
   int maxPoints(vector<Point> &points) {  
     int res = 0;  
     for (int i = 0; i < points.size(); i++) {  
       unordered_map<pair<int,int>,int,hashfunc> lines;  
       int localmax = 0, vertical = 0, overlap = 0;  
       for (int j = i + 1; j < points.size(); j++){  
         if (points[j].x == points[i].x && points[j].y == points[i].y){  
           overlap++;  
           continue;  
         } else if (points[j].x == points[i].x) {  
           vertical++;  
         } else {  
           int yd = points[j].y - points[i].y, xd = points[j].x - points[i].x;  
           int gcd = __gcd(yd, xd);  
           yd /= gcd;  
           xd /= gcd;  
           lines[{xd, yd}]++;  
           localmax = max(lines[{xd, yd}], localmax);  
         }  
         localmax = max(vertical, localmax);  
       }  
       res = max(res, localmax+overlap+1);  
     }    
     return res;  
   }  
 };