Leetcode 3235. 判断矩形的两个角落是否可达

 1 class Solution {
 2 public:
 3     bool canReachCorner(int xCorner, int yCorner, vector<vector<int>>& circles) {
 4         vector<bool> visited(circles.size(), false);
 5 
 6         function<bool(int)> dfs = [&](int i) -> bool {
 7             int x1 = circles[i][0], y1 = circles[i][1], r1 = circles[i][2];
 8             if (circleIntersectsBottomRightOfRectangle(x1, y1, r1, xCorner, yCorner)) {
 9                 return true;
10             }
11             visited[i] = true;
12             for (int j = 0; j < circles.size(); ++j) {
13                 int x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];
14                 if (!visited[j] && circlesIntersectInRectangle(x1, y1, r1, x2, y2, r2, xCorner, yCorner) && dfs(j)) {
15                     return true;
16                 }
17             }
18             return false;
19         };
20 
21         for (int i = 0; i < circles.size(); ++i) {
22             int x = circles[i][0], y = circles[i][1], r = circles[i][2];
23             if (pointInCircle(0, 0, x, y, r) || pointInCircle(xCorner, yCorner, x, y, r)) {
24                 return false;
25             }
26             if (!visited[i] && circleIntersectsTopLeftOfRectangle(x, y, r, xCorner, yCorner) && dfs(i)) {
27                 return false;
28             }
29         }
30         return true;
31     }
32 
33     bool pointInCircle(long long px, long long py, long long x, long long y, long long r) {
34         return (x - px) * (x - px) + (y - py) * (y - py) <= (long long)r * r;
35     }
36 
37     bool circleIntersectsTopLeftOfRectangle(int x, int y, int r, int xCorner, int yCorner) {
38         return (abs(x) <= r && 0 <= y && y <= yCorner) ||
39             (0 <= x && x <= xCorner && abs(y - yCorner) <= r) ||
40             pointInCircle(x, y, 0, yCorner, r);
41     }
42 
43     bool circleIntersectsBottomRightOfRectangle(int x, int y, int r, int xCorner, int yCorner) {
44         return (abs(y) <= r && 0 <= x && x <= xCorner) ||
45             (0 <= y && y <= yCorner && abs(x - xCorner) <= r) ||
46             pointInCircle(x, y, xCorner, 0, r);
47     }
48 
49     bool circlesIntersectInRectangle(long long x1, long long y1, long long r1, long long x2, long long y2, long long r2, long long xCorner, long long yCorner) {
50         return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2) &&
51             x1 * r2 + x2 * r1 < (r1 + r2) * xCorner &&
52             y1 * r2 + y2 * r1 < (r1 + r2) * yCorner;
53     }
54 };