<p>There is a 1 million by 1 million grid on an XY-plane, and the coordinates of each grid square are <code>(x, y)</code>.</p>

<p>We start at the <code>source = [s<sub>x</sub>, s<sub>y</sub>]</code> square and want to reach the <code>target = [t<sub>x</sub>, t<sub>y</sub>]</code> square. There is also an array of <code>blocked</code> squares, where each <code>blocked[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> represents a blocked square with coordinates <code>(x<sub>i</sub>, y<sub>i</sub>)</code>.</p>

<p>Each move, we can walk one square north, east, south, or west if the square is <strong>not</strong> in the array of <code>blocked</code> squares. We are also not allowed to walk outside of the grid.</p>

<p>Return <code>true</code><em> if and only if it is possible to reach the </em><code>target</code><em> square from the </em><code>source</code><em> square through a sequence of valid moves</em>.</p>

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

<pre>
<strong>Input:</strong> blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
<strong>Output:</strong> false
<strong>Explanation:</strong> The target square is inaccessible starting from the source square because we cannot move.
We cannot move north or east because those squares are blocked.
We cannot move south or west because we cannot go outside of the grid.
</pre>

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

<pre>
<strong>Input:</strong> blocked = [], source = [0,0], target = [999999,999999]
<strong>Output:</strong> true
<strong>Explanation:</strong> Because there are no blocked cells, it is possible to reach the target square.
</pre>

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

<ul>
	<li><code>0 &lt;= blocked.length &lt;= 200</code></li>
	<li><code>blocked[i].length == 2</code></li>
	<li><code>0 &lt;= x<sub>i</sub>, y<sub>i</sub> &lt; 10<sup>6</sup></code></li>
	<li><code>source.length == target.length == 2</code></li>
	<li><code>0 &lt;= s<sub>x</sub>, s<sub>y</sub>, t<sub>x</sub>, t<sub>y</sub> &lt; 10<sup>6</sup></code></li>
	<li><code>source != target</code></li>
	<li>It is guaranteed that <code>source</code> and <code>target</code> are not blocked.</li>
</ul>

class Solution:
    def isEscapePossible(self, blocked: List[List[int]], source: List[int], target: List[int]) -> bool:
        # Define the possible movements (Moore neighborhood)
        moves = [(-1, -1), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1)]
        rows,cols = 10**6,10**6
        def find_boundary(bk, start):
            boundary = []
            # Trace the boundary   
            r, c = start
            current_dir = 0
            while True:
                boundary.append((r, c))
                if len(boundary) > 600:
                    return None
                for i in range(8):
                    dir_index = (current_dir + i) % 8
                    dr, dc = moves[dir_index]
                    nr, nc = r + dr, c + dc
                    if nr >= -1 and nr < rows+1 and nc >= -1 and nc < cols+1 and ((nr,nc) in bk or nr==-1 or nr==rows or nc==-1 or nc==cols):
                        r, c = nr, nc
                        current_dir = (dir_index + 5) % 8
                        break
                if (r, c) == start:
                    break
                                    
            #-- remove repeated points
            m = len(boundary)
            h={}
            boundaryNew=[]
            for i in range(m):
                r,c = boundary[i]
                if (r,c) not in h:
                    boundaryNew.append((r,c))
                    h[(r,c)] = i
                else:
                    while boundaryNew and boundaryNew[-1] != (r,c):
                        boundaryNew.pop()

            return boundaryNew
                    
        def is_point_in_polygon(point, polygon):
            x,y = point
            num_vertices = len(polygon)
            intersect_count = 0

            for i in range(num_vertices):
                x1, y1 = polygon[i]
                x2, y2 = polygon[(i + 1) % num_vertices]

                # Check if the point is between the y-coordinates of the edge's endpoints
                if min(y1, y2) < y <= max(y1, y2):
                    if x <= max(x1, x2):
                        if y1 != y2:
                            x_intersection = (y - y1) * (x2 - x1) / (y2 - y1) + x1
                        if x1 == x2 or x <= x_intersection:
                            intersect_count += 1
            # If the number of intersections is odd, the point is inside the polygon
            return intersect_count % 2 == 1
        

        bk = {}
        for r,c in blocked:
            bk[(r,c)] = True

        blocked.sort()
        #source = tuple(source)
        #target = tuple(target)
        #-------------------- check source -----------------
        n = len(blocked)
        k = bisect.bisect_right(blocked,source)        
        while k <= n:
            if k==n: # not found any block on row r
                start = [source[0],cols]
            elif k < n and blocked[k][0] != source[0]:
                start = (source[0],cols)
                k = n
            else:
                start = tuple(blocked[k]) 

            #print(f"start={start}")     
            k += 1
            
            # Get the boundary of the region
            boundary = find_boundary(bk,start)
            #print(f"initinal boundary={boundary}")
            if boundary==None:                 
                sourceInside = False
                targetInside = False
            else:                
                if len(boundary) < 4:
                    sourceInside = False
                    targetInside = False
                else:
                    sourceInside = is_point_in_polygon(source, boundary)                
                    targetInside = is_point_in_polygon(target, boundary)
            
            if sourceInside == True and targetInside==True:
                return True
            if sourceInside == True and targetInside==False:
                return False
            if sourceInside == False and targetInside==True:
                return False


        #----- check target ----------------------------------
        n = len(blocked)
        k = bisect.bisect_right(blocked,target)        
        while k <= n:
            if k==n: # not found any block on row r
                start = [target[0],cols]
            elif k < n and blocked[k][0] != target[0]:
                start = (target[0],cols)
                k = n
            else:
                start = tuple(blocked[k]) 
                           
            #print(f"start={start}")     
            k += 1
            
            # Get the boundary of the region
            boundary = find_boundary(bk,start)
            #print(f"initinal boundary={boundary}")
            if boundary==None:                 
                sourceInside = False
                targetInside = False
            else:                
                if len(boundary) < 4:
                    sourceInside = False
                    targetInside = False
                else:
                    sourceInside = is_point_in_polygon(source, boundary)                
                    targetInside = is_point_in_polygon(target, boundary)
            
            if sourceInside == True and targetInside==True:
                return True
            if sourceInside == True and targetInside==False:
                return False
            if sourceInside == False and targetInside==True:
                return False

        return True
17100