how to use 2 integers to represent a double if 0 -> up = 0, do not represent inf if has sign, sign is on the up
| 33 | /// if 0 -> up = 0, do not represent inf |
| 34 | /// if has sign, sign is on the up |
| 35 | int maxPoints(vector<vector<int>>& points) { |
| 36 | // edge case |
| 37 | if (points.size() <= 2) return points.size(); |
| 38 | int res = 0; // max points on line |
| 39 | for (int i=0; i<points.size(); i++) { |
| 40 | map<pair<int,int>,int> lines; |
| 41 | int overlap = 0, vertical = 0; |
| 42 | |
| 43 | for (int j=i+1; j<points.size(); j++) { |
| 44 | // handle overlap cases |
| 45 | if (points[i][0] == points[j][0] and points[i][1] == points[j][1]){ |
| 46 | overlap ++ ; |
| 47 | continue; |
| 48 | } else if (points[i][0] == points[j][0]) { |
| 49 | vertical ++ ; |
| 50 | continue; |
| 51 | } else if (points[j][1] == points[i][1]) { |
| 52 | lines[make_pair(1, 0)] ++ ; |
| 53 | } else { |
| 54 | int a = points[j][0] - points[i][0], b = points[j][1] - points[i][1]; |
| 55 | // check sign of a and b, a and b are both not zero |
| 56 | if (a^b < 0 and a > 0) { |
| 57 | // different sign need to switch sign |
| 58 | a = -a; |
| 59 | b = -b; |
| 60 | } |
| 61 | int max_remainder = gcd(abs(a), b); // might overflow |
| 62 | a /= max_remainder; |
| 63 | b /= max_remainder; |
| 64 | lines[make_pair(a, b)] ++ ; |
| 65 | } |
| 66 | } |
| 67 | int localres = vertical; |
| 68 | for (auto i : lines) { |
| 69 | if (i.second > localres) localres = i.second; |
| 70 | // cout << i.first.first << i.first.second << i.second << endl; |
| 71 | } |
| 72 | res = max(res, localres + 1 + overlap); |
| 73 | } |
| 74 | return res; |
| 75 | } |
| 76 | }; |
| 77 | |
| 78 | int main() { |