<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>

class Solution {
public:
 
    int m_nMaxPoints = 0;

    class SlopeIntercept
    {
        public:
        SlopeIntercept()
        : m_dx(INT_MAX), m_dy(INT_MAX), m_yint(FLT_MAX)
        {}

        SlopeIntercept(int dx, int dy, float yint)
        : m_dx(dx), m_dy(dy), m_yint(yint)
        {}

        SlopeIntercept(const SlopeIntercept&) = default;
        SlopeIntercept& operator=(const SlopeIntercept&) = default;

        bool operator<(const SlopeIntercept& sl) const
        {
            if(m_dx == sl.m_dx)
            {
                if(m_dy == sl.m_dy)
                {
                    if(std::fabs(m_yint - sl.m_yint) < 0.0001)
                        return false;

                    return (m_yint < sl.m_yint);

                }
                return (m_dy < sl.m_dy);
            }

            return m_dx < sl.m_dx;
        }

        int m_dx = INT_MAX;
        int m_dy = INT_MAX;
        float m_yint = FLT_MAX;
    };
    
    class Line
    {
        public:
            Line(const vector<int>& start, const vector<int>& end)
            : m_pStart(start), m_pEnd(end)
            {
                m_si.m_dx = end[0] - start[0];
                m_si.m_dy = end[1] - start[1];

                if(0 == m_si.m_dx)
                {
                    m_si.m_dy = 0;
                    m_si.m_yint = end[0];
                }
                else
                {
                    float slope = float(m_si.m_dy) / float(m_si.m_dx);
                    m_si.m_yint = float(end[1]) - slope*float(end[0]);

                    //std::cout << "Slope=" << m_si.m_dy << " " << m_si.m_dx << " " << slope << " YInt=" << m_si.m_yint << std::endl;
                }

                int gcd = std::gcd(m_si.m_dx, m_si.m_dy);

                if(0 != gcd) {
                    m_si.m_dx /= gcd;
                    m_si.m_dy /= gcd;
                }
            }

            vector<int> m_pStart;
            vector<int> m_pEnd;

            SlopeIntercept m_si;
    };

    // Store lines by slope and intercept
    using PointSet = std::set< vector<int> >;

    std::map<SlopeIntercept, PointSet> m_mapLineToPoints;

    Line CalcLine(const vector<int>& p0, const vector<int>& p1) const
    {
        return Line(p0, p1);
    }

    void AddLine(const Line& l)
    {
        auto it = m_mapLineToPoints.find(l.m_si);
        if(m_mapLineToPoints.end() == it)
        {
            //std::cout << "Adding Line " << l.m_si.m_dx << " " << l.m_si.m_dy << " " << l.m_si.m_yint << std::endl;

            //for(auto element : m_mapLineToPoints)
            //{
           //     std::cout << element.first.m_dx << " " << element.first.m_dy 
           //     << " " << element.first.m_yint << " " << (element.first < l.m_si) << " " << (l.m_si < element.first) << std::endl;
           // }

            PointSet ps;
        ps.insert(l.m_pStart);
        ps.insert(l.m_pEnd);

        m_mapLineToPoints[l.m_si] = ps;

        if(ps.size() > m_nMaxPoints)
        {
            m_nMaxPoints = ps.size();
        }

        it = m_mapLineToPoints.find(l.m_si);

        //std::cout << "Find After Add " << (it != m_mapLineToPoints.end()) << std::endl;

        }
        else
        {
            //std::cout << "Found Line " << l.m_si.m_dx << " " << l.m_si.m_dy << " " << l.m_si.m_yint << std::endl;
        

        PointSet& ps = (*it).second;
        ps.insert(l.m_pStart);
        ps.insert(l.m_pEnd);

        if(ps.size() > m_nMaxPoints)
        {
            m_nMaxPoints = ps.size();
        }

        }
    }

    int GetMaxPoints() const
    {
        return m_nMaxPoints;
    }

    int maxPoints(vector<vector<int>>& points) {
        SlopeIntercept si1(-6,-25,-72);
        SlopeIntercept si2(-6,-25,-72);

        //std::cout << "si1 < si2 " << (si1 < si2) << " si2 < si1 " << (si2 < si1) << std::endl;
        
        if(points.size() <= 1)
            return points.size();

        int nMaxPoints = 0;

        for(std::size_t iPoint(0); iPoint < (points.size()-1); ++iPoint)
        {
            for(std::size_t iPoint2(iPoint+1); iPoint2 < points.size(); ++iPoint2)
            {
                // Calculate the line that iPoint and iPoint2 are on
                Line l = CalcLine(points[iPoint], points[iPoint2]);

                // Add the Line to the Line database
                AddLine(l);
            }
        }

       // for(auto it : m_mapLineToPoints)
       // {
       //     std::cout << "Slope " << it.first.m_dx << " " << it.first.m_dy << " YInt " << it.first.m_yint 
       //         << " Count " << it.second.size() << std::endl;
       // }

        return GetMaxPoints();
    }
};
66696