LeetCode - Max Points on a Line

  1 // 8CE, 1AC, solution with <map>, I‘ll try <unordered_map> later.
  2 #include <map>
  3 #include <vector>
  4 using namespace std;
  5 
  6 /*
  7 struct Point {
  8     int x;
  9     int y;
 10     Point() : x(0), y(0) {}
 11     Point(int a, int b) : x(a), y(b) {}
 12 };
 13 */
 14 
 15 struct st {
 16     int x;
 17     int y;
 18     st(int _x = 0, int _y = 0): x(_x), y(_y) {};
 19 
 20     bool operator == (const st &other) const {
 21         return x == other.x && y == other.y;
 22     }
 23 
 24     bool operator != (const st &other) const {
 25         return x != other.x || y != other.y;
 26     }
 27 
 28     bool operator < (const st &other) const {
 29         if (x == other.x) {
 30             return y < other.y;
 31         } else {
 32             return x < other.x;
 33         }
 34     }
 35 };
 36 
 37 class Solution {
 38 public:
 39     int maxPoints(vector<Point> &points) {
 40         int n = (int)points.size();
 41         
 42         if (n <= 2) {
 43             return n;
 44         }
 45         
 46         map<st, int> um;
 47         st tmp;
 48         // special tangent value for duplicate points
 49         st dup(0, 0);
 50         
 51         int i, j;
 52         map<st, int>::const_iterator umit;
 53         int dup_count;
 54         int max_count;
 55         int result = 0;
 56         for (i = 0; i < n; ++i) {
 57             for (j = i + 1; j < n; ++j) {
 58                 tmp.x = points[j].x - points[i].x;
 59                 tmp.y = points[j].y - points[i].y;
 60                 // make sure one tangent value has one representation only.
 61                 normalize(tmp);
 62                 if (um.find(tmp) != um.end()) {
 63                     ++um[tmp];
 64                 } else {
 65                     um[tmp] = 1;
 66                 }
 67             }
 68             max_count = dup_count = 0;
 69             for (umit = um.begin(); umit != um.end(); ++umit) {
 70                 if (umit->first != dup) {
 71                     max_count = (umit->second > max_count ? umit->second : max_count);
 72                 } else {
 73                     dup_count = umit->second;
 74                 }
 75             }
 76             max_count = max_count + dup_count + 1;
 77             result = (max_count > result ? max_count : result);
 78             um.clear();
 79         }
 80         
 81         return result;
 82     }
 83 private:
 84     void normalize(st &tmp) {
 85         if (tmp.x == 0 && tmp.y == 0) {
 86             // (0, 0)
 87             return;
 88         }
 89         if (tmp.x == 0) {
 90             // (0, 1)
 91             tmp.y = 1;
 92             return;
 93         }
 94         if (tmp.y == 0) {
 95             // (1, 0)
 96             tmp.x = 1;
 97             return;
 98         }
 99         if (tmp.x < 0) {
100             // (-2, 3) and (2, -3) => (2, -3)
101             tmp.x = -tmp.x;
102             tmp.y = -tmp.y;
103         }
104         
105         int gcd_value;
106         
107         gcd_value = (tmp.y > 0 ? gcd(tmp.x, tmp.y) : gcd(tmp.x, -tmp.y));
108         // (4, -6) and (-30, 45) => (2, -3)
109         // using a double precision risks in accuracy
110         // so I did it with a pair
111         tmp.x /= gcd_value;
112         tmp.y /= gcd_value;
113     }
114     
115     int gcd(int x, int y) {
116         // used for reduction of fraction
117         return y ? gcd(y, x % y) : x;
118     }
119 };