**Max Points on Line leetcode**

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

struct Point {

int x;

int y;

Point() : x(0), y(0) {}

Point(int a, int b) : x(a), y(b) {}

};

//The STL includes the ordered and the unordered map (std::map and std::unordered_map) containers.

// In an ordered map the elements are sorted by the key, insert and access is in O(log n)).

// Usually the STL internally uses red black trees for ordered maps. But this is just an implementation detail.

// In an unordered map insert and access is in O(1). It is just another name for a hashtable.

int maxPoints(vector<Point> &points) {

unordered_map<double, int> map ;

int ret = 0;

int size = points.size();

for (int i = 0; i < size; i++) {

int invalidK = 0;

int add = 1;

for (int j = i + 1; j < size; j++) {

if (points[j].x == points[i].x) {

if (points[j].y == points[i].y) {

add++;

} else {

invalidK++;

}

continue;

}

double k = points[j].y == points[i].y ? 0.0

: (1.0 * (points[j].y – points[i].y))

/ (points[j].x – points[i].x);

if (map.find( k ) != map.end()) {

int count = map[k];

map[k]= count + 1;

} else {

map[k]= 1;

}

}

typedef unordered_map<double, int>::iterator map_iterator;

for(map_iterator i = map.begin(); i != map.end(); i++) {

if(i->second + add > ret)

{

ret= i->second + add;

}

}

ret = max(invalidK + add, ret);

map.clear();

}

return ret;

}