drof13

Untitled

Jan 17th, 2022
74
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.23 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <iostream>
  4. #include <iterator>
  5. #include <map>
  6. #include <set>
  7. #include <string>
  8. #include <vector>
  9. #include <algorithm>
  10. #include <stack>
  11. #include <deque>
  12. #include <queue>
  13. #include <climits>
  14.  
  15. #define ll long long
  16. #define db double
  17. #define ff first
  18. #define ss second
  19.  
  20. using namespace std;
  21.  
  22. const int MOD = 1e9 + 7;
  23. // const int INF = LONG_MAX;
  24. const int INF = 1e9 + 7;
  25.  
  26. void dfs(int s, vector<vector<int>>& g, vector<bool>& used) {
  27.     if (used[s]) {
  28.         return;
  29.     }
  30.     used[s] = true;
  31.     for (auto i : g[s]) {
  32.         dfs(i, g, used);
  33.     }
  34. }
  35.  
  36. signed main() {
  37.     ios_base::sync_with_stdio(0);
  38.     cin.tie(0);
  39.     cout.tie(0);
  40.     int n;
  41.     cin >> n;
  42.     vector<int> x(n);
  43.     vector<int> y(n);
  44.     vector<int> z(n);
  45.     vector<int> r(n);
  46.     for (int i = 0; i < n; i++) {
  47.         cin >> x[i] >> y[i] >> z[i] >> r[i];
  48.     }
  49.     vector<vector<int>> g(n);
  50.     for (int i = 0; i < n; i++) {
  51.         for (int j = 0; j < n; j++) {
  52.             if (i == j || z[i] <= z[j]) {
  53.                 continue;
  54.             }
  55.             bool isEdge = false;
  56.             if (x[i] <= x[j]) {
  57.                 if (y[i] <= y[j]) {
  58.                     if (x[i] + r[i] >= x[j] - r[j] && y[i] + r[i] >= y[j] - r[j]) {
  59.                         isEdge = true;
  60.                     }
  61.                 } else if (x[i] + r[i] >= x[j] - r[j] && y[i] - r[i] <= y[j] + r[j]) {
  62.                     isEdge = true;
  63.                 }
  64.             } else {
  65.                 if (y[i] <= y[j]) {
  66.                     if (x[i] - r[i] <= x[j] + r[j] && y[i] + r[i] >= y[j] - r[j]) {
  67.                         isEdge = true;
  68.                     }
  69.                 } else if (x[i] - r[i] <= x[j] + r[j] && y[i] - r[i] <= y[j] + r[j]) {
  70.                     isEdge = true;
  71.                 }
  72.             }
  73.             if (isEdge) {
  74.                 g[i].push_back(j);
  75.             }
  76.         }
  77.     }
  78.     vector<bool> used(n, false);
  79.     dfs(0, g, used);
  80.     int ans = 0;
  81.     for (int i = 0; i < n; i++) {
  82.         if (used[i]) {
  83.             ans++;
  84.         }
  85.     }
  86.     cout << ans << '\n';
  87.     for (int i = 0; i < n; i++) {
  88.         if (used[i]) {
  89.             cout << i + 1 << " ";
  90.         }
  91.     }
  92. }
Advertisement
Add Comment
Please, Sign In to add comment