# LeetCode: 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.

This is tough as a line can have slope. My solution is O(n^2):

 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113 // //  main.cpp //  Max Points on a Line // //  Created by Yingbo Miao on 2014-08-30. //  Copyright (c) 2014 miao.fm. All rights reserved. // #include #include #include #include using namespace std; class Point { public:      int x;      int y;      Point() : x(0), y(0) {}      Point(int a, int b) : x(a), y(b) {} }; class Solution { public:     int maxPoints(vector &points) {         int ret = 0;                 if (points.empty()) {             return 0;         } else if (points.size() == 1) {             return 1;         }                 typedef unordered_map LineCnt;         LineCnt line_cnt;         LineCnt::iterator it_find;                                 double slope = std::numeric_limits::infinity();         int this_line = 0;         int point_a_max = 0;         int dup = 0;         for(unsigned long i = 0; i < points.size(); ++i) {             line_cnt.clear();             const Point& point_a = points.at(i);             point_a_max =  1;             dup = 0;             for(unsigned long j = i+1; j < points.size(); ++j) {                 if (j == i) {                     continue;                 }                 const Point& point_b = points.at(j);                                                                 if (point_b.x != point_a.x) {                                         slope = double(point_b.y - point_a.y) / (point_a.x - point_b.x);                 } else {                     if (point_b.y == point_a.y) {                         ++dup;                         continue;                     }                     slope = std::numeric_limits::infinity();                 }                 it_find = line_cnt.find(slope);                 //                cout << slope << " " << (it_find == line_cnt.end()) << endl;                                 if (it_find == line_cnt.end()) {                     line_cnt[slope]=2;                     this_line = 2;                 } else {                     //this_line = ++(it_find->second);                     this_line = ++(line_cnt[slope]);                                     }                                 if (this_line > point_a_max) {                     point_a_max = this_line;                 }             }                         point_a_max += dup;             if (point_a_max > ret) {                 ret = point_a_max;             }         }         return ret;             } }; int main(int argc, const char * argv[]) {     vector points;     Point point;     point.x = 4;     point.y = 0;     points.push_back(point);         point.x = 4;     point.y = -1;     points.push_back(point);         point.x = 4;     point.y = 5;     points.push_back(point);                 Solution r;     cout << r.maxPoints(points) << endl;     }