#include <bits/stdc++.h>
#include <iostream>
#include <queue>
using namespace std;
#define pb push_back
#define mp make_pair
#define rept(i, a, b) for (int i = a; i < b; i++)
#define rep(i, n) for (int i = 0; i < n; i++)
#define vec vector
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef vec<int> vi;
typedef vec<vi> v2i;
typedef pair<ll, ll> pl;
typedef pair<int, int> pi;
typedef vec<pl> vpl;
typedef vec<pi> vpi;
typedef vec<bool> vb;
typedef priority_queue<pair<int, pi>> qpi;
typedef priority_queue<int> qi;
//sub 1-5
ll ct(pl c1, pl c2, pi d1, pi d2) {
if (d1==d2) return 0;
pi rel = {d1.first - d2.first, d1.second - d2.second};
//cout << "calculating collide time" << endl;
ll t = max(abs(c2.first - c1.first), abs(c2.second - c1.second)) / max(abs(rel.first), abs(rel.second));
//cout << "t = " << t << endl;
if (c1.first + t*rel.first == c2.first && c1.second + t*rel.second == c2.second) return max(t, (ll)0);
return 0;
}
void sub1(int n, vpl& c, vpi& d) {
if (ct(c[0], c[1], d[0], d[1]) == 0) {
cout << "1 2 \n";
}
}
void sub5(int n, vpl& c, vpi& d) {
qpi q;
rep(i, n-1) {
rept(j, i+1, n) {
int t = ct(c[i], c[j], d[i], d[j]);
if (t!=0) {
q.push({-t, {i, j}});
}
}
}
vb s(n, true);
while (!q.empty()) {
int t = q.top().first;
//cout << "at time " << -t << ": ";
qi sh;
while (!q.empty() && q.top().first == t) {
int i = q.top().second.first, j = q.top().second.second;
q.pop();
if (s[i]) sh.push(i);
if (s[j]) sh.push(j);
}
if (sh.size() > 1) {
while (!sh.empty()) {
//cout << sh.top() << " ";
s[sh.top()] = false;
sh.pop();
}
}// else cout << sh.top();
//cout << endl;
}
rep(i, n) {
if (s[i]) cout << i+1 << " ";
} cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vpl c(n);
vpi d(n);
rep(i,n) {
char dir;
cin >> c[i].first >> c[i].second >> dir;
if (dir=='N') d[i] = {0, -1};
if (dir=='E') d[i] = {1, 0};
if (dir=='S') d[i] = {0, 1};
if (dir=='W') d[i] = {-1, 0};
}
//cout << "done input" << endl;
if (n==2) sub1(n, c, d);
else sub5(n,c,d);
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |