Pagini recente » Cod sursa (job #732290) | Cod sursa (job #1072190) | Cod sursa (job #74693) | Cod sursa (job #2203650) | Cod sursa (job #1074517)
#include <fstream>
#include <algorithm>
#include <iostream>
using namespace std;
ifstream fin ("zc.in");
ofstream fout ("zc.out");
const int N = 14e5 + 5;
pair <int, int> vx[N], vy[N];
int n, m, x, y, k, kx;
long long sol;
int abs(int x) {
return (x > -x ? x : -x);
}
int last_query(pair<int, int> v[N], pair <int, int> P) {
if (P > v[k-1])
return k;
int poz = -1;
for (int step = (1 << 17); step; step >>=1)
if (poz + step < k && v[poz + step] <= P)
poz += step;
return poz;
}
int first_query(pair <int, int> v[N], pair <int, int> P) {
if (P > v[k-1])
return k;
int poz = -1;
for (int step = (1 << 17); step; step >>= 1)
if (poz + step < k && v[poz + step] < P)
poz += step;
return poz;
}
int main() {
fin >> n >> m;
while (n--) {
int x, y;
fin >> x >> y;
for (int i = -2; i <= 2; ++i)
for (int j = -2; j <= 2; ++j)
if (abs(i) + abs(j) <= 2 && (x+i || y+j))
vx[kx++] = make_pair (x+i, y+j);
}
sort (vx, vx + kx);
for (int i = 0; i < kx; ++i)
if (!i || vx[i] != vx[i-1])
vx[k++] = vx[i];
for (int i = 0; i < k; ++i)
vy[i] = make_pair (vx[i].second, vx[i].first);
sort (vy, vy + k);
while (m--) {
char d; int dist;
fin >> d >> dist;
if (d == 'S') {
sol += last_query(vx, make_pair(x, y)) - first_query(vx, make_pair (x, y - dist));
y -= dist;
}
if (d == 'N') {
sol += last_query(vx, make_pair(x, y + dist)) - first_query(vx, make_pair (x, y));
y += dist;
}
if (d == 'V') {
sol += last_query(vy, make_pair(y, x)) - first_query(vy, make_pair(y, x - dist));
x -= dist;
}
if (d == 'E') {
sol += last_query(vy, make_pair(y, x + dist)) - first_query(vy, make_pair(y, x));
x +=dist;
}
int poz = last_query(vx, make_pair (x, y));
if (vx[poz] == make_pair (x, y) && m)
sol--;
}
fout << sol;
}