题目：Given n points on a 2D plane, find the maximum number
of points that lie on the same straight line.（给的点是用vector保
存）
/** * Definition for a point. * struct Point { * int x; * int y; * Point() : x(0), y(0) {} * Point(int a, int b) : x(a), y(b) {} * }; */思路：
构建双重for循环，相当于起始点与终点
一个起始点和斜率可以确定一条直线，用map<double, int>来保存对应的斜率与该直线上出现的点数的值
三种情况：重合点（用dup来保存），斜率不存在的垂直点（用vertical来保存），斜率可算的正常情况
class Solution { public: int maxPoints(vector<Point> &points) { int size = points.size(); if(size < 0)return -1; if(size == 0)return 0; if(size == 1)return 1; map<double, int> mymap; int res = 0; //the final result for(int i = 0; i < size; ++i){ int vertical = 0; //垂直点 int dup = 0; //重合点duplicate int curmax = 1; for(int j = 0; j < size; ++j){ if(i != j){ double delt_x = points[i].x - points[j].x; //delt_* must be declared double double delt_y = points[i].y - points[j].y; if((int)delt_y == 0 && (int)delt_x == 0){ //重合点 dup++; }else if(delt_x == 0){ //垂直点 if(vertical == 0)vertical = 2; else vertical++; curmax = max(vertical, curmax); }else{ //common situation double k = delt_y / delt_x; if(mymap[k] == 0)mymap[k] = 2; else mymap[k]++; curmax = max(mymap[k], curmax); } } } res = max(res, curmax+dup); } return res; } };