思路:并查集,如果两个点可以相互传达,就是两个集合的合并,当然,前提是要两个点都被维修过。
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <queue> 5 #include <vector> 6 #include <cmath> 7 8 using namespace std; 9 10 #define ll long long 11 #define pb push_back 12 #define fi first 13 #define se second 14 15 const int N = 1010; 16 vector<pair<int ,int > > vp; 17 int G[N][N]; 18 int fa[N], vis[N]; 19 int n, d; 20 21 inline int dis(int x, int y) 22 { 23 return (vp[x].fi - vp[y].fi) * (vp[x].fi - vp[y].fi) + (vp[x].se - vp[y].se) * (vp[x].se - vp[y].se); 24 } 25 26 void build() 27 { 28 for(int i = 0; i < n; ++i){ 29 for(int j = 0; j < n; ++j){ 30 G[i][j] = dis(i, j); 31 } 32 } 33 } 34 35 int Find(int x) 36 { 37 return fa[x] == x ? x : fa[x] = Find(fa[x]); 38 } 39 40 void Union(int x, int y) 41 { 42 int fax = Find(x); 43 int fay = Find(y); 44 45 if(fax == fay) return; 46 fa[fax] = fay; 47 } 48 49 void solve() 50 { 51 scanf("%d%d", &n, &d); 52 d *= d; 53 int xx, yy; 54 for(int i = 0; i < n; ++i){ 55 scanf("%d%d", &xx, &yy); 56 vp.pb({xx, yy}); 57 } 58 59 build(); 60 61 for(int i = 0; i < n; ++i) fa[i] = i; 62 63 char op[2]; 64 int x, y; 65 while(~scanf("%s", op)){ 66 if(op[0] == ‘O‘){ 67 scanf("%d", &x); 68 vis[--x] = 1;//标记该点被修理过 69 for(int i = 0; i < n; ++i){ 70 if(i != x && G[x][i] <= d && vis[i]){ 71 Union(x, i); 72 } 73 } 74 }else{ 75 scanf("%d%d", &x, &y); 76 int fax = Find(--x); 77 int fay = Find(--y); 78 if(fax == fay) printf("SUCCESS\n"); 79 else printf("FAIL\n"); 80 } 81 } 82 } 83 84 int main() 85 { 86 87 solve(); 88 89 return 0; 90 }