PROBLEM LINK:
Author: Sumit
Tester: Neeraj
Editorialist: Manish
DIFFICULTY:
EASY.
PREREQUISITES:
Math STL.
PROBLEM:
Sherlock is following N criminals, which are right now in a 2D grid. Each criminal at t=0, decides to move in a certain fixed direction. Each criminal moves with the same speed. These fixed directions are North, East, West and South. Two or more criminals, however, vanish whenever they meet at any place at the same time, t>0. You have to tell what is the final number of criminals left at t=infinity. Note: No two criminals will have the same starting point at t=0.
EXPLANATION:
simulate the intersections between criminals in ascending order of time. for each criminal, it will have a related direction (dx,dy) such that the criminal’s position after t time units will be: (x[i] + dx[i]*t, y[i] + dy[i]*t). ( (dx,dy) can be (0,1), (0,-1), (1,0) or (-1,0) and depend on direction[i] ). Each of these rules make an equation and you can find the intersection between each pairs of equations (if it exists). Sort the intersection in non-decreasing order. And for each intersection between non-erased criminals in the correct order, erase the criminals that intersect.
SOLUTIONS:
Setter's Solution
indent whole code by 4 spaces
Tester's Solution
indent whole code by 4 spaces
Editorialist's Solution
#include <iostream>
using namespace std;
struct pkt
{
int x, y;
char kier;
bool jest;
};
int main()
{
ios_base::sync_with_stdio(0);
int t;
cin >> t;
for (int i = 0; i < t; ++i)
{
int n;
cin >> n;
vector p(n);
for (int j = 0; j < n; ++j)
{
cin >> p[j].x >> p[j].y >> p[j].kier;
p[j].x *= 2;
p[j].y *= 2;
p[j].jest = true;
}
for (int j = 0; j < 4000; ++j)
{
for (int k = 0; k < n; ++k)
{
if (p[k].jest)
{
if (p[k].kier == ‘N’) ++p[k].y;
if (p[k].kier == ‘S’) --p[k].y;
if (p[k].kier == ‘E’) ++p[k].x;
if (p[k].kier == ‘W’) --p[k].x;
}
}
for (int k = 0; k < n; ++k)
{
if (p[k].jest)
{
vector nry;
for (int l = 0; l < n; ++l)
{
if (l != k && p[l].jest && p[l].x == p[k].x && p[l].y == p[k].y)
{
nry.push_back(l);
p[l].jest = false;
}
}
if (nry.size() != 0) nry.push_back(k);
for (int l = 0; l < nry.size(); ++l) p[nry[l]].jest = false;
}
}
}
int il = 0;
for (int j = 0; j < n; ++j)
if (p[j].jest) ++il;
cout << il << endl;
}
return 0;
}