<p>A robot on an infinite XY-plane starts at point <code>(0, 0)</code> facing north. The robot receives an array of integers <code>commands</code>, which represents a sequence of moves that it needs to execute. There are only three possible types of instructions the robot can receive:</p>

<ul>
	<li><code>-2</code>: Turn left <code>90</code> degrees.</li>
	<li><code>-1</code>: Turn right <code>90</code> degrees.</li>
	<li><code>1 &lt;= k &lt;= 9</code>: Move forward <code>k</code> units, one unit at a time.</li>
</ul>

<p>Some of the grid squares are <code>obstacles</code>. The <code>i<sup>th</sup></code> obstacle is at grid point <code>obstacles[i] = (x<sub>i</sub>, y<sub>i</sub>)</code>. If the robot runs into an obstacle, it will stay in its current location (on the block adjacent to the obstacle) and move onto the next command.</p>

<p>Return the <strong>maximum squared Euclidean distance</strong> that the robot reaches at any point in its path (i.e. if the distance is <code>5</code>, return <code>25</code>).</p>

<p><strong>Note:</strong></p>

<ul>
	<li>There can be an obstacle at <code>(0, 0)</code>. If this happens, the robot will ignore the obstacle until it has moved off the origin. However, it will be unable to return to <code>(0, 0)</code> due to the obstacle.</li>
	<li>North means +Y direction.</li>
	<li>East means +X direction.</li>
	<li>South means -Y direction.</li>
	<li>West means -X direction.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [4,-1,3], obstacles = []</span></p>

<p><strong>Output:</strong> <span class="example-io">25</span></p>

<p><strong>Explanation: </strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 4 units to <code>(0, 4)</code>.</li>
	<li>Turn right.</li>
	<li>Move east 3 units to <code>(3, 4)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(3, 4)</code>, which squared is <code>3<sup>2</sup> + 4<sup>2 </sup>= 25</code> units away.</p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [4,-1,4,-2,4], obstacles = [[2,4]]</span></p>

<p><strong>Output:</strong> <span class="example-io">65</span></p>

<p><strong>Explanation:</strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 4 units to <code>(0, 4)</code>.</li>
	<li>Turn right.</li>
	<li>Move east 1 unit and get blocked by the obstacle at <code>(2, 4)</code>, robot is at <code>(1, 4)</code>.</li>
	<li>Turn left.</li>
	<li>Move north 4 units to <code>(1, 8)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(1, 8)</code>, which squared is <code>1<sup>2</sup> + 8<sup>2</sup> = 65</code> units away.</p>
</div>

<p><strong class="example">Example 3:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">commands = [6,-1,-1,6], obstacles = [[0,0]]</span></p>

<p><strong>Output:</strong> <span class="example-io">36</span></p>

<p><strong>Explanation:</strong></p>

<p>The robot starts at <code>(0, 0)</code>:</p>

<ol>
	<li>Move north 6 units to <code>(0, 6)</code>.</li>
	<li>Turn right.</li>
	<li>Turn right.</li>
	<li>Move south 5 units and get blocked by the obstacle at <code>(0,0)</code>, robot is at <code>(0, 1)</code>.</li>
</ol>

<p>The furthest point the robot ever gets from the origin is <code>(0, 6)</code>, which squared is <code>6<sup>2</sup> = 36</code> units away.</p>
</div>

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

<ul>
	<li><code>1 &lt;= commands.length &lt;= 10<sup>4</sup></code></li>
	<li><code>commands[i]</code> is either <code>-2</code>, <code>-1</code>, or an integer in the range <code>[1, 9]</code>.</li>
	<li><code>0 &lt;= obstacles.length &lt;= 10<sup>4</sup></code></li>
	<li><code>-3 * 10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 3 * 10<sup>4</sup></code></li>
	<li>The answer is guaranteed to be less than <code>2<sup>31</sup></code>.</li>
</ul>

class Solution {
    int ans;
public:

    int findMaxStep( int changeCord, int fixCord, vector<int> obs, bool pos , int v)
    {
        cout << "inside function"<<endl;

        cout << " Change cord: " << changeCord << " fixed cord: " << fixCord << " " << pos << endl;
        cout << " printing obstacles " << endl;
        for(const auto &itr:obs)
        {
            cout<< (itr) << " ";
        }
        cout <<endl;
        cout << "-------------------------" << endl;
        // if(!obs.size() || )
        // {
        //     // cout << "no obstacles" << endl;
        //     return v;
        // }
        
        // if(pos && obs[obs.size()-1]<=changeCord)
        // {
        //     cout << "no obstacles last smaller" << endl;
        //     return v;
        // }
        
        // if(!pos && obs[0]>=changeCord)
        // {
        //     cout << "no obstacles last smaller" << endl;
        //     return v;
        // }

        int l =0, r= obs.size()-1, mid;
        int idx{-1};
        while(l<=r)
        {
            mid = (l+r)/2;
            if(obs[mid] == changeCord)
            {
                if(pos)
                    idx = mid+1;
                else
                    idx= mid-1;
                break;
            }
            else if(obs[mid]>changeCord)
                r = mid-1;
            else
                l = mid+1;
        }
        if(idx==-1)
            idx = pos?l:r;

        cout << "final " << idx << endl;
        
        if(pos && idx>=obs.size())
        {
            cout << "no obstacles last smaller" << endl;
            return v;
        }
        
        if(!pos && idx<0)
        {
            cout << "no obstacles first greater" << endl;
            return v;
        }

        return pos?min(v,abs(obs[idx] - changeCord -1)):min(v,abs(obs[idx] - changeCord +1));

    }

    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        
        sort(obstacles.begin(), obstacles.end(), [](const vector<int> &a, const vector<int> &b)
        {
            if(a[0] == b[0])
                return a[1]<b[1];
            return a[0]<b[0];

        });
        int x{},y{};
        vector< vector < int> > pDir = {{0,1},
                                        {1,0},
                                        {0,-1},
                                        {-1,0}};
        int cDir = 0;
        unordered_map<int, vector<int> > xobs; // obstacles if we are proceeding in y direction with x fixed.
        unordered_map<int, vector<int> > yobs; // obstacles if we are proceeding in x direction with y fixed.

        for( auto &o:obstacles)
        {
            xobs[o[0]].push_back(o[1]);
            yobs[o[1]].push_back(o[0]);
        }
        
        for(auto &v:commands)
        {
            if(v==0)
                continue;
            if(v<0)
            {
                if(v ==-2)
                    cDir--;
                else
                    cDir++;

                cDir = (cDir +  4)%4;
                cout << cDir << endl;
            }
            else
            {
                bool pos = false;
                bool procX = true;
                if(cDir == 0 || cDir == 1)
                    pos = true;
                
                if(cDir == 0 || cDir == 2)
                    procX = false;

                if(procX)
                {
                    //we will proceed in x direction
                    //so we should look in yobs

                    int maxV = findMaxStep(x, y, yobs[y], pos, v);
                    cout <<"Proceeding in x: "<<  maxV << " " << cDir << " " << pos << endl;
                    x += maxV*pDir[cDir][0];;

                }
                else
                {
                    int maxV = findMaxStep(y, x, xobs[x], pos, v);
                    cout <<"Proceeding in y: "<<  maxV << " " << cDir << " " << pos << endl;
                    y += maxV*pDir[cDir][1];;
                }

                ans = max(ans,x*x + y*y);
                cout << x<< " " << y << " " << ans << " -----" << endl;
            }
        }

        return ans;
    }
};
48743