check-if-the-rectangle-corner-is-reachable

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given two positive integers <code>xCorner</code> and <code>yCorner</code>, and a 2D array <code>circles</code>, where <code>circles[i] = [xi, yi, ri]</code> denotes a circle with center at <code>(xi, yi)</code> and radius <code>ri</code>.

There is a rectangle in the coordinate plane with its bottom left corner at the origin and top right corner at the coordinate <code>(xCorner, yCorner)</code>. You need to check whether there is a path from the bottom left corner to the top right corner such that the entire path lies inside the rectangle, does not touch or lie inside any circle, and touches the rectangle only at the two corners.

Return <code>true</code> if such a path exists, and <code>false</code> otherwise.

&nbsp;
Example 1:

<div class="example-block">
Input: xCorner = 3, yCorner = 4, circles = [[2,1,1]]

Output: true

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example2circle1.png" style="width: 346px; height: 264px;" />

The black curve shows a possible path between <code>(0, 0)</code> and <code>(3, 4)</code>.
</div>

Example 2:

<div class="example-block">
Input: xCorner = 3, yCorner = 3, circles = [[1,1,2]]

Output: false

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example1circle.png" style="width: 346px; height: 264px;" />

No path exists from <code>(0, 0)</code> to <code>(3, 3)</code>.
</div>

Example 3:

<div class="example-block">
Input: xCorner = 3, yCorner = 3, circles = [[2,1,1],[1,2,1]]

Output: false

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example0circle.png" style="width: 346px; height: 264px;" />

No path exists from <code>(0, 0)</code> to <code>(3, 3)</code>.
</div>

Example 4:

<div class="example-block">
Input: xCorner = 4, yCorner = 4, circles = [[5,5,1]]

Output: true

Explanation:

<img alt="" src="https://assets.leetcode.com/uploads/2024/08/04/rectangles.png" style="width: 346px; height: 264px;" />
</div>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= xCorner, yCorner &lt;= 109</code></li>
	<li><code>1 &lt;= circles.length &lt;= 1000</code></li>
	<li><code>circles[i].length == 3</code></li>
	<li><code>1 &lt;= xi, yi, ri &lt;= 109</code></li>
</ul>

canReachCorner

Check if the Rectangle Corner Is Reachable

Queries on Number of Points Inside a Circle

queries-on-number-of-points-inside-a-circle

统计一个圆中点的数目

Check if Point Is Reachable

check-if-point-is-reachable

判断一个点是否可以到达

Depth-First Search

Breadth-First Search

Union Find

Geometry

Array

Math

给你两个正整数&nbsp;<code>xCorner</code> 和&nbsp;<code>yCorner</code>&nbsp;和一个二维整数数组&nbsp;<code>circles</code>&nbsp;，其中&nbsp;<code>circles[i] = [xi, yi, ri]</code>&nbsp;表示一个圆心在&nbsp;<code>(xi, yi)</code>&nbsp;半径为&nbsp;<code>ri</code>&nbsp;的圆。

坐标平面内有一个左下角在原点，右上角在&nbsp;<code>(xCorner, yCorner)</code>&nbsp;的矩形。你需要判断是否存在一条从左下角到右上角的路径满足：路径&nbsp;完全&nbsp;在矩形内部，不会&nbsp;触碰或者经过 任何&nbsp;圆的内部和边界，同时&nbsp;只 在起点和终点接触到矩形。

如果存在这样的路径，请你返回&nbsp;<code>true</code>&nbsp;，否则返回&nbsp;<code>false</code>&nbsp;。

&nbsp;

示例 1：

<div class="example-block">
输入：X = 3, Y = 4, circles = [[2,1,1]]

输出：true

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example2circle1.png" style="width: 346px; height: 264px;" />

黑色曲线表示一条从&nbsp;<code>(0, 0)</code>&nbsp;到&nbsp;<code>(3, 4)</code>&nbsp;的路径。
</div>

示例 2：

<div class="example-block">
输入：X = 3, Y = 3, circles = [[1,1,2]]

输出：false

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example1circle.png" style="width: 346px; height: 264px;" />

不存在从&nbsp;<code>(0, 0)</code> 到&nbsp;<code>(3, 3)</code>&nbsp;的路径。
</div>

示例 3：

<div class="example-block">
输入：X = 3, Y = 3, circles = [[2,1,1],[1,2,1]]

输出：false

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/05/18/example0circle.png" style="width: 346px; height: 264px;" />

不存在从&nbsp;<code>(0, 0)</code>&nbsp;到&nbsp;<code>(3, 3)</code>&nbsp;的路径。
</div>

示例 4：

<div class="example-block">
输入：X = 4, Y = 4, circles = [[5,5,1]]

输出：true

解释：

<img alt="" src="https://assets.leetcode.com/uploads/2024/08/04/rectangles.png" style="width: 346px; height: 264px;" />
</div>

&nbsp;

提示：

<ul>
	<li><code>3 &lt;= xCorner, yCorner&nbsp;&lt;= 109</code></li>
	<li><code>1 &lt;= circles.length &lt;= 1000</code></li>
	<li><code>circles[i].length == 3</code></li>
	<li><code>1 &lt;= xi, yi, ri &lt;= 109</code></li>
</ul>