建立一个网站如何开通账号,怎么做网页公证,网站建设和管理办法,额敏网站建设题意
传送门 LeeCode AutoX-4 蚂蚁爬行
题解
枚举每一对几何图形#xff0c;判断相交性#xff0c;用并查集维护连通性即可。总时间复杂度 O ( n 2 m ) O(n^2 m) O(n2m)#xff0c;其中 n n n 为几何图形数量#xff0c; m m m 为查询数量。
根据几何图形性质分类讨…题意
传送门 LeeCode AutoX-4 蚂蚁爬行
题解
枚举每一对几何图形判断相交性用并查集维护连通性即可。总时间复杂度 O ( n 2 m ) O(n^2 m) O(n2m)其中 n n n 为几何图形数量 m m m 为查询数量。
根据几何图形性质分类讨论。
判断两圆相交令 d d d 表示圆心距离 r 1 , r 2 ( r 1 ≤ r 2 ) r1,r2(r1\leq r2) r1,r2(r1≤r2) 分别为两圆半径则充要条件为 r 2 − r 1 ≤ d ≤ r 1 r 2 r2 - r1 \leq d \leq r1 r2 r2−r1≤d≤r1r2。
判断两线段相交一类思路是计算出交点在判断交点是否处于两条线段上由于只用判断相交性不用求交点可以使用基于ccw函数的做法简单求解具体而言用端点表示的两条非平行的线段 ( p 1 , p 2 ) , ( q 1 , q 2 ) (p1,p2),(q1,q2) (p1,p2),(q1,q2)对其中任意线段 ( p 1 , p 2 ) (p1, p2) (p1,p2) 而言另一条线段 ( q 1 , q 2 ) (q1, q2) (q1,q2) 的两个端点必然在 ( p 1 , p 2 ) (p1, p2) (p1,p2) 所在直线的两侧或者至多一个端点位于直线上此时可以通过叉积简单地进行判断。
判断线段与圆的相交性若圆心到线段所在直线的最小距离大于半径则不可能相交反之若线段存在位于圆上的端点则相交若线段存在位于圆内部的端点则除了两个端点都位于圆内的情况其他情况都相交其余情况圆心与线段两端点的连线都位于圆心与线段的垂线两侧此时可以通过内积简单地进行判断。
#include bits/stdc.h
using namespace std;
using ll long long;
using lll __int128;
struct Point {ll x, y;Point operator(Point o) {return {x o.x, y o.y};}Point operator-(Point o) {return {x - o.x, y - o.y};}ll dot(Point o) {return x * o.x y * o.y;}ll det(Point o) {return x * o.y - o.x * y;}
};
struct DSU {vectorint par;DSU(int n) : par(n) {iota(par.begin(), par.end(), 0);}int find(int x) {return par[x] x ? x : (par[x] find(par[x]));}void unite(int x, int y) {x find(x), y find(y);par[x] y;}bool same(int x, int y) {return find(x) find(y);}
};
class Solution {public:vectorbool antPass(vectorvectorint geometry, vectorvectorint path) {int n geometry.size();DSU dsu(n);auto on_seg [](Point p, Point q1, Point q2) {return (q1 - p).det(q2 - p) 0 (q1 - p).dot(q2 - p) 0;};auto intersection [](Point p1, Point p2, Point q1, Point q2) {auto f [](Point p1, Point p2, Point q1, Point q2) {return (lll)(p1 - p2).det(q1 - p2) * (p1 - p2).det(q2 - p2) 0;};if ((p1 - p2).det(q1 - q2) 0) {return on_seg(p1, q1, q2) || on_seg(p2, q1, q2) || on_seg(q1, p1, p2) || on_seg(q2, p1, p2);}return f(p1, p2, q1, q2) f(q1, q2, p1, p2);};auto in_circle [](Point p, Point q, ll r) {return (p - q).dot(p - q) r * r;};auto on_circle [](Point p, Point q, ll r) {return (p - q).dot(p - q) r * r;};for (int i 0; i n; i) {for (int j 0; j i; j) {int n geometry[i].size(), m geometry[j].size();if (n m) {if (n 3) {ll dx geometry[i][0] - geometry[j][0];ll dy geometry[i][1] - geometry[j][1];ll r geometry[i][2] geometry[j][2];ll l max(geometry[i][2], geometry[j][2]) - min(geometry[i][2], geometry[j][2]);if (dx * dx dy * dy r * r dx * dx dy * dy l * l) {dsu.unite(i, j);}} else {Point p1 {geometry[i][0], geometry[i][1]};Point p2 {geometry[i][2], geometry[i][3]};Point q1 {geometry[j][0], geometry[j][1]};Point q2 {geometry[j][2], geometry[j][3]};if (intersection(p1, p2, q1, q2)) {dsu.unite(i, j);}}} else {auto a geometry[i], b geometry[j];if (a.size() 3) {swap(a, b);}Point p1 {a[0], a[1]};Point p2 {a[2], a[3]};Point q {b[0], b[1]};ll r b[2];lll d (p1 - p2).det(p1 - q);if (d * d (lll)(p1 - p2).dot(p1 - p2) * r * r) {int can 0;if (on_circle(p1, q, r) || on_circle(p2, q, r)) {can 1;} else if (in_circle(p1, q, r) || in_circle(p2, q, r)) {can !(in_circle(p1, q, r) in_circle(p2, q, r));} else if (((p1 - q).dot(p1 - p2) 0) ! ((p2 - q).dot(p1 - p2) 0)) {can 1;}if (can) {dsu.unite(i, j);}}}}}int m path.size();vectorbool res(m);for (int i 0; i m; i) {res[i] dsu.same(path[i][0], path[i][1]);}return res;}
};
