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

Solution:

/** * 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:    double PI = 3.1415926;        double computeAngle(int x, int y, int xx, int yy){  if(x == xx)  {    if(y == yy)      return 2 * PI;    else      return PI;  }  else    return atan((double)(yy - y) / (xx - x));}int maxPoints(vector
     
       &points) {        int n = points.size();        if(n <= 2) return n;        double **angle = new double*[n + 1];        int **visited = new int*[n + 1];        for(int i = 0;i < n;i++)        {         angle[i] = new double[n + 1];         visited[i] = new int[n + 1];        }        for(int i = 0;i < n;i++)         {          memset(visited[i], 0, (n + 1) * sizeof(int));          for(int j = i;j < n;j++)           angle[i][j] = angle[j][i] = computeAngle(points[i].x, points[i].y, points[j].x, points[j].y);         }        int max = 2;        for(int i = 0;i < n;i++)        {          for(int j = 0;j < n;j++)          {            if(i == j || visited[i][j] == 1) continue;            visited[i][j] = 1;            //define a line by point i and j            double curAngle = angle[i][j];            int curNum = 2;            for(int k = 0;k < n;k++)            {              if(i != k && j != k)              {               if(curAngle == 2 * PI)               {                if(angle[i][k] == 2 * PI || angle[j][k] == 2 * PI)                {                 curNum++;                }                else                {                  curNum++;                  curAngle = angle[i][k];                  visited[i][k] = visited[j][k] = visited[k][j] = visited[k][i] = 1;                }               }               else               {                  if(angle[i][k] == curAngle)                  {                    curNum++;                    visited[i][k] = visited[j][k] = visited[k][j] = visited[k][i] = 1;                  }               }                   }            }          //  cout << i << " " << j << " :" <
      
       << endl;            max = (curNum > max) ? curNum : max;          }        }        return max;    }};