Max points on any line among set of points.

solution-lc-maxPoints.cpp

inline std::size_t hash_combine(std::size_t hash1, std::size_t hash2) {
    return hash1 ^ (hash2 * 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2));
}

struct Hasher2 {
  size_t operator() (const tuple<int,int>& val) const {
      return hash_combine(hash<int>{}(get<0>(val)), hash<int>{}(get<1>(val)));
  } 
};

struct Hasher3 {
  size_t operator() (const tuple<int,int,int>& val) const {
      return hash_combine(hash<int>{}(get<0>(val)), hash_combine(hash<int>{}(get<1>(val)), hash<int>{}(get<2>(val))));
  }
};

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        if (points.size() <= 2) return points.size();
        
        unordered_map< tuple<int,int>, int, Hasher2 > dublicates(points.size());
        // get rid of dublicates
        for (auto& p : points) {
            ++dublicates[{p[0], p[1]}];
        }
        
        unordered_map< tuple<int,int,int>, int, Hasher3> cnt;
        int n = points.size();
        for (int i = 0; i < n; ++i) {
            int cntPoint1 = dublicates[{points[i][0], points[i][1]}];
            for (int j = i + 1; j < n; ++j) {
                int cntPoint2 = dublicates[{points[j][0], points[j][1]}];
                int ny = points[i][0] - points[j][0];
                int nx = -(points[i][1] - points[j][1]);
                if (nx == 0 && ny == 0) {// dublicate
                    continue;
                }
                
                // find canonical form
                int g = __gcd(nx, ny);
                if (g != 0) {
                    nx /= g; ny /= g;
                }
                if (nx == 0) ny = 1;
                if (ny == 0) nx = 1;
                if (nx < 0) { // reverse if it points down
                    nx *= -1;
                    ny *= -1;
                }
                int cosval = -(nx * points[i][0]  + ny * points[i][1]);
                cnt[{nx, ny, cosval}] += cntPoint2;
            }
        }
        
        int maxCnt = 0; // these are for the real line
        for (auto& kv : cnt) {
            maxCnt = max(maxCnt, kv.second);
        }
        int maxDublicates = 0; // this is for many points with the same coords
        for (auto& kv: dublicates)
            maxDublicates = max(maxDublicates, kv.second);
        // because we will count it many times:
        // For each point we will count this point and n-1 pairing points
        // so the total number is n^2 - n
        // But here we count each pair once so 2*maxCount = n^2 - n
        return max((double)maxDublicates, (1 + sqrt(1 + 4 * 2 * maxCnt))/2);
    }
};