当前位置:   article > 正文

P3958 [NOIP2017 提高组] 奶酪(并查集)_csp 奶酪 并查集

csp 奶酪 并查集

[NOIP2017 提高组] 奶酪 - 洛谷https://www.luogu.com.cn/problem/P3958

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <queue>
  7. #include <stack>
  8. #include <cstring>
  9. #include <set>
  10. #include <cmath>
  11. #include <map>
  12. #include <cstdlib>
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15. using namespace std;
  16. const int MN = 65005;
  17. const int MAXN = 2000010;
  18. const int INF = 0x3f3f3f3f;
  19. #define IOS ios::sync_with_stdio(false)
  20. int pre[MAXN];
  21. int find(int x) {
  22. if (pre[x] == x) {
  23. return x;
  24. }
  25. return pre[x] = find(pre[x]);
  26. }
  27. ll dis(ll x1, ll y1, ll z1, ll x2, ll y2, ll z2) {
  28. return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2) + (z1 - z2) * (z1 - z2);
  29. }
  30. ll x[10005], y[10005], z[10005];
  31. int f1[10001], f2[100005];
  32. inline bool same(int x, int y) {
  33. return find(x) == find(y);
  34. }
  35. int main() {
  36. int t;
  37. scanf("%d", &t);
  38. int n, h;
  39. ll r;
  40. while (t--) {
  41. scanf("%d %d %lld", &n, &h, &r);
  42. int cnt1 = 0;
  43. int cnt2 = 0;
  44. for (int i = 1; i <= n; i++) {
  45. pre[i] = i;
  46. }
  47. for (int i = 1; i <= n; i++) {
  48. scanf("%lld %lld %lld", x + i, y + i, z + i);
  49. if (z[i] + r >= h) {
  50. cnt1++;
  51. f1[cnt1] = i;
  52. }
  53. if (z[i] - r <= 0) {
  54. cnt2++;
  55. f2[cnt2] = i;
  56. }
  57. for (int j = 1; j < i; j++) {
  58. if (dis(x[i], y[i], z[i], x[j], y[j], z[j]) <= 4 * r * r) {
  59. pre[find(i)] = find(j);
  60. }
  61. }
  62. }
  63. bool flag=true;
  64. for (int i = 1; i <= cnt1; i++) {
  65. for (int j = 1; j <= cnt2; j++) {
  66. if (same(f1[i], f2[j])) {
  67. printf("Yes\n");
  68. flag =false;
  69. break;
  70. }
  71. }
  72. if (!flag) {
  73. break;
  74. }
  75. }
  76. if(flag){
  77. printf("No\n");
  78. }
  79. }
  80. return 0;
  81. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/空白诗007/article/detail/792406
推荐阅读
  

闽ICP备14008679号