<p>Given an array of <code>points</code> where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> represents a point on the <strong>X-Y</strong> plane, return <em>the maximum number of points that lie on the same straight line</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/25/plane1.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[2,2],[3,3]]
<strong>Output:</strong> 3
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/02/25/plane2.jpg" style="width: 300px; height: 294px;" />
<pre>
<strong>Input:</strong> points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
<strong>Output:</strong> 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= points.length &lt;= 300</code></li>
	<li><code>points[i].length == 2</code></li>
	<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
	<li>All the <code>points</code> are <strong>unique</strong>.</li>
</ul>

#define DEBUG 0

// Hash function 
struct hashFunction  
{ 
  size_t operator()(const vector<int>  
                    &myVector) const 
  { 
    std::hash<int> hasher; 
    size_t answer = 0; 
      
    for (int i : myVector)  
    { 
      answer ^= hasher(i) + 0x9e3779b9 +  
                (answer << 6) + (answer >> 2); 
    } 
    return answer; 
  } 
}; 

class Solution {
public:
    int maxPoints(vector<vector<int>>& points) {
        std::unordered_map<std::string, std::unordered_set<vector<int>, hashFunction>> m; 

        for (int i = 0; i < points.size(); i++) {
            for (int j = i + 1; j < points.size(); j++) {
                // y = m * x + b
                // key = concat(m, b)
                // solve for m = (y_2 - y_1) / (x_2 - x_1)
                // solve for b = y_1 - m * x_1
                if (DEBUG) std::cout << "(" + to_string(points[i][0]) + ", " + to_string(points[i][1]) + ") (" + to_string(points[j][0]) + ", " + to_string(points[j][1]) + ")" << std::endl; 
                // the "100 * " in key is just a padder to help with floating point precision. to_string seems to truncate doubles after a number of digits
                std::string key = 
                        (points[i][0] - points[j][0]) == 0 ? "VERT " + to_string(points[i][0]) : 
                        (points[i][1] - points[j][1]) == 0 ? "HORZ " + to_string(points[i][1]) : 
                        to_string((double) 100 * (points[i][1] - points[j][1]) / (points[i][0] - points[j][0])) + " " + 
                        to_string((double) points[i][1] - (double) (points[i][1] - points[j][1]) / (points[i][0] - points[j][0]) * (double) points[i][0]);
                if (DEBUG) std::cout << key << std::endl;

                // std::unordered_set<vector<int>, hashFunction> temp{points[i], points[j]};
                // m.insert({key, temp});

                m[key].insert(points[i]);
                m[key].insert(points[j]);
                

            }
        }

        int max_count = 1;
        for (auto const& i : m) {
            if (DEBUG) {
                std::cout << "key: " + i.first + " val: ";
                for (auto const & j : i.second) {
                    std::cout << "(" + to_string(j[0]) + ", " + to_string(j[1]) + ") ";
                }
                std::cout << std::endl;
            }
            if (i.second.size() > max_count) max_count = i.second.size(); 
        }
        return max_count;
    }
};
63268