Pagini recente » Profil LitaAndrei | Cod sursa (job #2284741) | Cod sursa (job #2224043) | Cod sursa (job #3282466) | Cod sursa (job #1730658)
#include <fstream>
#include <algorithm>
#define x first
#define y second
using namespace std;
ifstream fin ("zc.in");
ofstream fout ("zc.out");
int N, M, Px, Py, cx, cy, nrel, nr, dist, s1, s2, sol;
pair < int, int > A[1300000], B[1300000];
char dir;
int Modul(int val)
{
if (val < 0) val *= -1;
return val;
}
int Caut_Binar(int X, int Y, pair < int, int > V[])
{
int p = 1, u = nr, mij;
pair < int, int > val;
val.x = X; val.y = Y;
if (V[nr] <= val) return nr + 1;
while (p < u)
{
mij = (p + u) / 2;
if (V[mij] <= val) p = mij + 1;
else u = mij;
}
return p;
}
int main()
{
fin >> N >> M;
for (int k=1; k<=N; k++)
{
fin >> cx >> cy;
for (int i=-2; i<=2; i++)
{
for (int j=-2; j<=2; j++)
{
if (Modul(i) + Modul(j) <= 2 && (cx + i || cy + j))
{
A[++nrel].x = cx + i;
A[nrel].y = cy + j;
}
}
}
}
sort (A + 1, A + 1 + nrel);
for (int i=1; i<=nrel; i++)
{
if (A[i].x != A[i-1].x || A[i].y != A[i-1].y)
{
A[++nr] = A[i];
B[nr].x = A[i].y;
B[nr].y = A[i].x;
}
}
sort (B + 1, B + 1 + nr);
for (int i=1; i<=M; i++)
{
fin >> dir >> dist;
switch (dir)
{
case 'N' :
{
s1 = Caut_Binar(Px, Py, A);
Py += dist;
s2 = Caut_Binar(Px, Py, A);
break;
}
case 'S' :
{
s2 = Caut_Binar(Px, Py - 1, A);
Py -= dist;
s1 = Caut_Binar(Px, Py - 1, A);
break;
}
case 'E' :
{
s1 = Caut_Binar(Py, Px, B);
Px += dist;
s2 = Caut_Binar(Py, Px, B);
break;
}
case 'V' :
{
s2 = Caut_Binar(Py, Px - 1, B);
Px -= dist;
s1 = Caut_Binar(Py, Px - 1, B);
break;
}
}
sol += s2 - s1;
}
fout << sol << '\n';
fout.close();
return 0;
}