Pagini recente » Cod sursa (job #2199074) | Cod sursa (job #456337) | Cod sursa (job #2061732) | Cod sursa (job #673112) | Cod sursa (job #1074371)
#include <fstream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;
ifstream fin ("zc.in");
ofstream fout ("zc.out");
map <int, vector <pair <int, int> > > MX, MY;
int n, m, xi, yi;
vector <int> vx, vy;
long long sol;
int abs(int x) {
return (x > -x ? x : -x);
}
long long query(vector <pair <int, int> > v, int lo, int hi) {
int poz = -1;
for (unsigned step = (1 << 17); step; step >>= 1)
if (poz + step < v.size() && v[poz + step].second < lo)
poz += step;
long long s = 0;
for (unsigned i = poz + 1; i < v.size() && v[i].first <= hi; ++i) {
int val;
if (i == poz + 1)
val = min(hi, v[i].second) - max(lo, v[i].first) + 1;
else
val = min(hi, v[i].second) - max(v[i].first, v[i-1].second + 1) + 1;
if (val > 0)
s += val;
}
return s;
}
int main() {
fin >> n >> m;
while (n--) {
int x, y;
fin >> x >> y;
for (int i = -2; i <= 2; ++i) {
MX[x+i].push_back (make_pair (y - 2 + abs(i), y + 2 - abs(i)));
MY[y+i].push_back (make_pair (x - 2 + abs(i), x + 2 - abs(i)));
vx.push_back (x + i);
vy.push_back (y + i);
}
}
sort (vx.begin(), vx.end());
sort (vy.begin(), vy.end());
int last = -1;
for (vector <int> :: iterator it = vx.begin(); it != vx.end(); ++it)
if (last == -1 || vx[last] != *it) {
sort (MX[*it].begin(), MX[*it].end());
last = it - vx.begin();
}
last = -1;
for (vector <int> :: iterator it = vy.begin(); it != vy.end(); ++it)
if (last == -1 || vy[last] != *it) {
sort (MY[*it].begin(), MY[*it].end());
last = it - vy.begin();
}
while (m--) {
char d; int dist;
fin >> d >> dist;
if (d == 'S') {
sol += query(MX[xi], yi - dist, yi);
yi -= dist;
}
if (d == 'N') {
sol += query(MX[xi], yi, yi + dist);
yi += dist;
}
if (d == 'E') {
sol += query(MY[yi], xi, xi + dist);
xi += dist;
}
if (d == 'V') {
sol += query(MY[yi], xi - dist, xi);
xi -= dist;
}
}
fout << sol;
}