Pagini recente » Cod sursa (job #3130587) | Cod sursa (job #2541450) | Cod sursa (job #1171080) | Cod sursa (job #522777) | Cod sursa (job #500902)
Cod sursa(job #500902)
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cassert>
using namespace std;
#define pii pair<int,int>
#define ff first
#define ss second
#define maxN 100100
#define maxM 2000000
#define all(v) v.begin(), v.end()
pii A[maxN], now, next;
vector < pii > X, Y;
int N, M, Nxy, Sol;
void baga_marfa (int x) {
int i, j;
for (i = -2; i <= 2; ++ i)
for (j = -2; j <= 2; ++ j)
if (abs(i) + abs(j) <= 2 && (A[x].ff + i || A[x].ss + j )) {
X.push_back(make_pair(A[x].ff + i, A[x].ss + j));
Y.push_back(make_pair(A[x].ss + j, A[x].ff + i));
}
}
void do_it (int c, int val) {
next = now;
vector < pii > :: iterator it1, it2;
pii tmp;
if (c == 'N') {
next.ss += val;
it1 = upper_bound(all(X), now);
it2 = upper_bound(all(X), next);
Sol += abs(it2 - it1);
} else if (c == 'S') {
next.ss -= val;
tmp = now;
it1 = lower_bound(all(X), next);
it2 = lower_bound(all(X), tmp);
Sol += abs(it2 - it1);
} else if (c == 'V') {
next.ff -= val;
tmp = make_pair ( next.ss, next.ff ) ;/*tmp.ff = next.ss;
tmp.ss = next.ff;*/
it1 = lower_bound(all(Y), tmp);
tmp = make_pair ( now.ss, now.ff ) ;/* tmp.ff = now.ss;
tmp.ss = now.ff;*/
it2 = lower_bound(all(Y), tmp);
Sol += abs(it2 - it1);
} else {
next.ff += val;
tmp = make_pair ( now.ss, now.ff ) ;/*tmp.ff = now.ss;
tmp.ss = now.ff;*/
it1 = upper_bound(all(Y), tmp);
tmp = make_pair ( next.ss, next.ff ) ;/*tmp.ff = next.ss;
tmp.ss = next.ff;*/
it2 = upper_bound(all(Y), tmp);
Sol += abs(it2 - it1);
}
now = next;
}
int main () {
int i, val;
vector < pii > :: iterator it;
char c;
freopen("zc.in", "r", stdin);
freopen("zc.out", "w", stdout);
scanf("%d%d", &N, &M);
for (i = 1; i <= N; ++ i) {
scanf("%d%d", &A[i].ff, &A[i].ss);
baga_marfa (i);
}
sort (X.begin(), X.end());
X.resize(unique(X.begin(), X.end()) - X.begin());
sort (Y.begin(), Y.end());
Y.resize(unique(Y.begin(), Y.end()) - Y.begin());
for (; M -- ;) {
scanf(" %c %d", &c, &val);
assert(c == 'V' || c == 'E' || c == 'N' || c == 'S');
do_it (c, val);
}
printf("%d\n", Sol);
}