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

#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <fstream>
#include <map>
#include <stack>

using namespace std;


//Definition for a binary tree node.
// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode() : val(0), left(nullptr), right(nullptr) {}
//     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
//     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
// };
class Solution {
public:
    int robotSim(vector<int>& commands, vector<vector<int>>& obstacles) {
        // -1 : turn left | -2 : turn right
        vector<vector<int>> direction = {{0, 1}, {1, 0}, {0,-1}, {-1, 0}}; // turn left-> -1 turn right-> +1;
        int start = 0;
        int x = 0;
        int y = 0;
        int ret = 0;
        sort(obstacles.begin(), obstacles.end());
        unordered_map<int, vector<int>> x_ob, y_ob;
        for(auto &ob: obstacles) {
            x_ob[ob[0]].push_back(ob[1]);
            y_ob[ob[1]].push_back(ob[0]);
        }
        for(int &command: commands) {
            if(command == -2) {
                start = (start-1+4)%4;
            } else if (command == -1) {
                start = (start+1)%4;
            } else {
                // cout<<start<<endl;
                int bound;
                if(start == 0) { //觀察x_ob上的最靠緊x且大於x的點;
                    bound = find_point(x_ob[x] , true, y);
                    if(bound > y+command) {
                        y+=command;
                    } else {
                        y = bound - 1;
                    }
                } else if (start == 1) { ////觀察y_ob上的最靠緊y且大於y的點;
                    bound = find_point(y_ob[y] , true, x);
                    if(bound > x+command) {
                        x+=command;
                       
                    } else {
                        x = bound - 1;
                    }
                } else if(start == 2) { //觀察x_ob上的最靠緊x且小於x的點;
                    bound = find_point(x_ob[x] , false, y);
                    if(bound >= y-command) {
                        y = bound + 1;
                    } else {
                       y-=command;
                    }
                } else { //觀察y_ob上的最靠緊y且小於y的點;
                    bound = find_point(y_ob[y] , false, x);
                    if(bound >= x-command) {
                       x = bound + 1;
                    } else {
                       x-=command;
                    }
                }
                // vector<string> sssss = {"+Y", "+X", "-Y", "-X"};
                // printf("start:%s, command:%d, bound: %d\nX:%d, Y:%d\n-------\n",sssss[start].c_str(), command, bound, x, y);
                ret = max (ret, x*x+y*y);
            }
        }
        return ret;

    }
    int find_point(vector<int> &vec, bool find_bigger, int val) {
        // cout<<"vec: ";
        // for(int i: vec) cout<<i<<" ";
        // cout<<endl;
        int n = vec.size();
        int left = 0;
        int right = n-1;
        if(right == -1) {
            if(find_bigger) return INT_MAX;
            else return INT_MIN;
        }
        int mid = (left+right)/2;
        while(left < right) {
            // cout<<val<<vec[mid]<<endl;
            mid = (left+right)/2;
            if(val == vec[mid]) break;
            if(val < vec[mid]) {
                right = mid-1;
            } else {
                left = mid+1;
            }
        }
        mid = (left+right)/2;
        int v = vec[mid];
        //cout<<"mid:"<<mid<<endl;
        if(v == val) {
            if(find_bigger) {
                if(mid == n-1)
                    return INT_MAX;
                else 
                    return vec[mid+1];

            } else {
                if(mid == 0) {
                    return INT_MIN;
                } else {
                    return vec[mid-1];
                }
            }
        } else if(v > val) {
            if(find_bigger) {
                return v;
            } else {
                if(mid == 0) {
                    return INT_MIN;
                } else {
                    return vec[mid-1];
                }
            }
        } else {
            if(find_bigger) {
                if(mid == n-1)
                    return INT_MAX;
                else 
                    return vec[mid+1];
            } else {
                return v;
            }
        }
        return -9999;
    }
};
// int main () {
//     Solution sol;
    
//     // cout<<sol.minMoves2(8);
//     return 0;
// }

48366