您的位置:首页 > 文旅 > 美景 > 昌大建设总部哪里_十大求职招聘app排行_免费推广渠道有哪些_引流推广是什么意思

昌大建设总部哪里_十大求职招聘app排行_免费推广渠道有哪些_引流推广是什么意思

2024/12/23 11:50:32 来源:https://blog.csdn.net/qq_41529799/article/details/143637120  浏览:    关键词:昌大建设总部哪里_十大求职招聘app排行_免费推广渠道有哪些_引流推广是什么意思
昌大建设总部哪里_十大求职招聘app排行_免费推广渠道有哪些_引流推广是什么意思

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

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

如果存在这样的路径,请你返回 true ,否则返回 false 。

今天的困难题是真的困难,以前的虽然也难,但至少我知道我是能写出来的,而今天的题目,一看就知道是个数学几何,而且看数据范围就知道还得套其他方法,只能说完全没有思路。

没办法,只能看题解了。看完题解之后发现,这居然是套了个基础的图论。如果不考虑图形相交的写法的话,这个题目要是能把想到把圆和边抽象出来的话,这题目也没那么难。

方法是这样的,把整个n个圆和矩形的4条边都抽象成图里的点,如果他们有相交,就把图里的点进行连线,那么要判断矩形的两个角落是否可达就可以简单的变成判断图里的四条矩形边任意两条是否联通,如果联通了,那么说明存在一些圆横跨了矩形的左右或者上下或者堵住了一个角落,也就是说不可达,否则就意味这可达。

贴个官方的题解和灵神的题解

class Solution {// 判断点 (x,y) 是否在圆 (ox,oy,r) 内bool in_circle(long long ox, long long oy, long long r, long long x, long long y) {return (ox - x) * (ox - x) + (oy - y) * (oy - y) <= r * r;}public:bool canReachCorner(int X, int Y, vector<vector<int>>& circles) {int n = circles.size();vector<int> vis(n);auto dfs = [&](auto&& dfs, int i) -> bool {long long x1 = circles[i][0], y1 = circles[i][1], r1 = circles[i][2];// 圆 i 是否与矩形右边界/下边界相交相切if (y1 <= Y && abs(x1 - X) <= r1 ||x1 <= X && y1 <= r1 ||x1 > X && in_circle(x1, y1, r1, X, 0)) {return true;}vis[i] = true;for (int j = 0; j < n; j++) {long long x2 = circles[j][0], y2 = circles[j][1], r2 = circles[j][2];// 在两圆相交相切的前提下,点 A 是否严格在矩形内if (!vis[j] && (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) <= (r1 + r2) * (r1 + r2) &&x1 * r2 + x2 * r1 < (r1 + r2) * X &&y1 * r2 + y2 * r1 < (r1 + r2) * Y &&dfs(dfs, j)) {return true;}}return false;};for (int i = 0; i < n; i++) {long long x = circles[i][0], y = circles[i][1], r = circles[i][2];if (in_circle(x, y, r, 0, 0) || // 圆 i 包含矩形左下角in_circle(x, y, r, X, Y) || // 圆 i 包含矩形右上角// 圆 i 是否与矩形上边界/左边界相交相切!vis[i] && (x <= X && abs(y - Y) <= r ||y <= Y && x <= r ||y > Y && in_circle(x, y, r, 0, Y)) && dfs(dfs, i)) {return false;}}return true;}
};

代码其实也没那么长,很大部分还是在于对几何相交的处理。

时间复杂度O(n*n),空间复杂度O(n).

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com