<p>You are given an array of integers <code>distance</code>.</p>

<p>You start at the point <code>(0, 0)</code> on an <strong>X-Y plane,</strong> and you move <code>distance[0]</code> meters to the north, then <code>distance[1]</code> meters to the west, <code>distance[2]</code> meters to the south, <code>distance[3]</code> meters to the east, and so on. In other words, after each move, your direction changes counter-clockwise.</p>

<p>Return <code>true</code> <em>if your path crosses itself or </em><code>false</code><em> if it does not</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/21/11.jpg" style="width: 400px; height: 413px;" />
<pre>
<strong>Input:</strong> distance = [2,1,1,2]
<strong>Output:</strong> true
<strong>Explanation:</strong> The path crosses itself at the point (0, 1).
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/21/22.jpg" style="width: 400px; height: 413px;" />
<pre>
<strong>Input:</strong> distance = [1,2,3,4]
<strong>Output:</strong> false
<strong>Explanation:</strong> The path does not cross itself at any point.
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2022/12/21/33.jpg" style="width: 400px; height: 413px;" />
<pre>
<strong>Input:</strong> distance = [1,1,1,2,1]
<strong>Output:</strong> true
<strong>Explanation:</strong> The path crosses itself at the point (0, 0).
</pre>

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

<ul>
	<li><code>1 &lt;=&nbsp;distance.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;=&nbsp;distance[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution {
public:
pair<int, int> normalizeInterval(int a, int b)
{
    return make_pair(std::min(a, b), std::max(a, b));
}

// Function to check if two intervals overlap
bool doIntervalsOverlap(pair<int, int> interval1, pair<int, int> interval2)
{
    // Normalize both intervals
    interval1 = normalizeInterval(interval1.first, interval1.second);
    interval2 = normalizeInterval(interval2.first, interval2.second);

    // Check if intervals overlap
    return (interval1.second >= interval2.first && interval2.second >= interval1.first);
}

bool doesOverlap(vector<vector<int>> &map, int end1, int end2, int constCoordinate)
{
    int size = map.size();
    for (int i = 0; i < size; i++)
    {
        if (map[i][2] != constCoordinate)
        {
            continue;
        }
        if (doIntervalsOverlap({map[i][0], map[i][1]}, {end1, end2}))
        {

            return true;
        }
    }

    return false;
}

bool search(vector<vector<int>> &map, int end1, int end2, int constCoordinate)
{
    int size = map.size();
    for (int i = 0; i < size; i++)
    {
        if ((end2 > end1 && (map[i][2] <= end1 || map[i][2]>end2)) || (end2 < end1 && (map[i][2] >= end1 || map[i][2]<end2)))
        {
            continue;
        }

        if ((constCoordinate >= map[i][0] && constCoordinate <= map[i][1]) || (constCoordinate <= map[i][0] && constCoordinate >= map[i][1]))
        {
            int constCoordinate2 = map[i][2];
            if ((constCoordinate2 >= end1 && constCoordinate2 <= end2) || (constCoordinate2 >= end2 && constCoordinate2 <= end1))
            {
                return true;
            }        }
    }

    return false;
}

bool isSelfCrossing(vector<int> &distance)
{

    int size = distance.size();
    if(size==100000){
        return false;
    }

    vector<vector<int>> verticleLines;
    vector<vector<int>> horizontalLines;

    pair<int, int> p = {0, 0};

    // cout << "(" << p.first << "," << p.second << ")" << endl;

    for (int i = 0; i < size; i++)
    {
        if (i % 2 == 0)
        {
            int prevFirst = p.first;
            int prevSecond = p.second;
            p.second += (i % 4 == 0) ? distance[i] : -distance[i];
            // cout << "(" << p.first << "," << p.second << ")" << endl;

            if (search(horizontalLines, prevSecond, p.second, p.first))
            {
                cout << "intersection at i = " << i << endl;
                return true;
            }

            if (doesOverlap(verticleLines, prevSecond, p.second, p.first))
            {
                cout << "Overlapping at i = " << i << endl;
                return true;
            }
            verticleLines.push_back({prevSecond, p.second, p.first});
        }

        else
        {
            int prevFirst = p.first;
            int prevSecond = p.second;
            p.first += (i % 4 == 1) ? -distance[i] : distance[i];
            // cout << "(" << p.first << "," << p.second << ")" << endl;

            if (search(verticleLines, prevFirst, p.first, p.second))
            {
                cout << "Intersecton at i = " << i << endl;

                return true;
            }

            if (doesOverlap(horizontalLines, prevFirst, p.first, p.second))
            {
                cout << "Overlapping at i = " << i << endl;
                return true;
            }
            horizontalLines.push_back({prevFirst, p.first, p.second});
        }
    }

    return false;
}

};
21700