Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cmath>
- #include <iostream>
- #include <iterator>
- #include <map>
- #include <set>
- #include <string>
- #include <vector>
- #include <algorithm>
- #include <stack>
- #include <deque>
- #include <queue>
- #include <climits>
- #define ll long long
- #define db double
- #define ff first
- #define ss second
- using namespace std;
- const int MOD = 1e9 + 7;
- // const int INF = LONG_MAX;
- const int INF = 1e9 + 7;
- void dfs(int s, vector<vector<int>>& g, vector<bool>& used) {
- if (used[s]) {
- return;
- }
- used[s] = true;
- for (auto i : g[s]) {
- dfs(i, g, used);
- }
- }
- signed main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0);
- cout.tie(0);
- int n;
- cin >> n;
- vector<int> x(n);
- vector<int> y(n);
- vector<int> z(n);
- vector<int> r(n);
- for (int i = 0; i < n; i++) {
- cin >> x[i] >> y[i] >> z[i] >> r[i];
- }
- vector<vector<int>> g(n);
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- if (i == j || z[i] <= z[j]) {
- continue;
- }
- bool isEdge = false;
- if (x[i] <= x[j]) {
- if (y[i] <= y[j]) {
- if (x[i] + r[i] >= x[j] - r[j] && y[i] + r[i] >= y[j] - r[j]) {
- isEdge = true;
- }
- } else if (x[i] + r[i] >= x[j] - r[j] && y[i] - r[i] <= y[j] + r[j]) {
- isEdge = true;
- }
- } else {
- if (y[i] <= y[j]) {
- if (x[i] - r[i] <= x[j] + r[j] && y[i] + r[i] >= y[j] - r[j]) {
- isEdge = true;
- }
- } else if (x[i] - r[i] <= x[j] + r[j] && y[i] - r[i] <= y[j] + r[j]) {
- isEdge = true;
- }
- }
- if (isEdge) {
- g[i].push_back(j);
- }
- }
- }
- vector<bool> used(n, false);
- dfs(0, g, used);
- int ans = 0;
- for (int i = 0; i < n; i++) {
- if (used[i]) {
- ans++;
- }
- }
- cout << ans << '\n';
- for (int i = 0; i < n; i++) {
- if (used[i]) {
- cout << i + 1 << " ";
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment