Pagini recente » Cod sursa (job #1393578) | Cod sursa (job #533143) | Cod sursa (job #714722) | Cod sursa (job #1966983) | Cod sursa (job #1263043)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define mp make_pair
using namespace std;
ifstream f ("zc.in");
ofstream g ("zc.out");
const int NMAX = 100000 + 1;
int n, m;
vector < pair <int, int> > capcane, capcane2;
int v[100];
bool inside(int x, int y) {
if (x < 0 || y < 0) return false;
return true;
}
inline int modul(int x) {
if (x > 0) return x;
return -x;
}
void citeste() {
f >> n >> m;
int a, b;
for (int i = 1; i <= n; i++) {
f >> a >> b;
for (int dx = -2; dx <= 2; dx++)
for (int dy = -2; dy <= 2; dy++)
if ((a + dx || b + dy) && (modul(dx) + modul(dy) <= 2)) {
capcane.push_back(make_pair(a + dx, b + dy));
}
}
}
int cauta_stanga(pair <int, int> loc, vector < pair <int, int> > capcane) {
int sol = 0, st = 0, dr = capcane.size() - 1, m;
while (st <= dr) {
m = (st + dr) / 2;
if (capcane[m] <= loc) {sol = m + 1; st = m + 1;}
else {dr = m - 1;}
}
return sol;
}
int cauta_dreapta(pair <int, int> loc, vector < pair <int, int> > capcane) {
int sol = -1, st = 0, dr = capcane.size() - 1, m;
while (st <= dr) {
m = (st + dr) / 2;
if (capcane[m] == loc) dr = m - 1;
else if (capcane[m] >= loc) {sol = m; dr = m - 1;}
else {st = m + 1;}
}
if (sol == -1) return capcane.size();
return sol;
}
void rezolva() {
sort(capcane.begin(), capcane.end());
capcane.resize(unique(capcane.begin() , capcane.end()) - capcane.begin());
n = 0;
for (int i = 1; i < capcane.size(); i++)
if (capcane[i] != capcane[i - 1])
capcane[++n] = capcane[i];
capcane.resize(n + 1);
for (int i = 0; i < capcane.size(); i++) capcane2.push_back(make_pair(capcane[i].second, capcane[i].first));
sort (capcane2.begin(), capcane2.end());
int X = 0, Y = 0, sol = 0;
char c; int d;
while (m--) {
f >> c >> d;
if (c == 'N') {
sol += cauta_dreapta(make_pair(X, Y + d), capcane) - cauta_stanga(make_pair(X, Y + 1), capcane);
Y += d;
}
else if (c == 'S') {
sol += cauta_dreapta(make_pair(X, Y - 1), capcane) - cauta_stanga(make_pair(X, Y - d), capcane);
Y -= d;
}
else if (c == 'E') {
sol += cauta_dreapta(make_pair(Y, X + d), capcane2) - cauta_stanga(make_pair(Y, X + 1), capcane2);
X += d;
}
else {
sol += cauta_dreapta(make_pair(Y, X - 1), capcane2) - cauta_stanga(make_pair(Y, X - d), capcane2);
X -= d;
}
}
g << sol << '\n';
}
int main() {
citeste();
rezolva();
return 0;
}