Pagini recente » Cod sursa (job #601826) | Cod sursa (job #1518349) | Cod sursa (job #2713573) | Cod sursa (job #2706597) | Cod sursa (job #866241)
Cod sursa(job #866241)
#include<fstream>
#include<algorithm>
using namespace std;
#define MAXCELL 1400000
typedef struct
{
int x, y;
} cell;
int N, M, i, j, x, y, k, nr_cells, t1, t2, res;
char c;
cell A;
cell v[ MAXCELL ];
inline int cmp(cell A, cell B)
{
if(A.x > B.x)
return 0;
if(A.x == B.x && A.y > B.y)
return 0;
return 1;
}
inline int search(cell A)
{
int st = 1, end = nr_cells, mid;
cell B;
while(st <= end)
{
mid = (st + end) / 2;
B = v[mid];
if(B.x < A.x)
st = mid + 1;
else if(B.x > A.x)
end = mid - 1;
else
{
if(B.y < A.y)
st = mid + 1;
else if(B.y > A.y)
end = mid - 1;
else return 1;
}
}
return 0;
}
int main()
{
ifstream f("zc.in");
ofstream g("zc.out");
f >> N >> M;
for(i = 1; i <= N; ++i)
{
f >> x >> y;
for(t1 = -2; t1 <= 2; ++t1)
for(t2 = -2; t2 <= 2; ++t2)
if(abs(t1) + abs(t2) <= 2)
++nr_cells, v[nr_cells].x = x + t1, v[nr_cells].y = y + t2;
}
sort(v+1, v+nr_cells+1, cmp);
v[0].x = v[1].x - 1;
for(i = 1; i <= nr_cells; ++i)
if(v[i].x != v[i-1].x || v[i].y != v[i-1].y)
++k, v[k].x = v[i].x, v[k].y = v[i].y;
nr_cells = k;
x = y = 0;
for(i = 1; i <= M; ++i)
{
f >> c >> k;
switch(c)
{
case 'N':
{
for(j = 1; j <= k; ++j)
{
++y, A.x = x, A.y = y;
if(x || y)
res += search(A);
}
} break;
case 'S':
{
for(j = 1; j <= k; ++j)
{
--y, A.x = x, A.y = y;
if(x || y)
res += search(A);
}
} break;
case 'V':
{
for(j = 1; j <= k; ++j)
{
--x, A.x = x, A.y = y;
if(x || y)
res += search(A);
}
} break;
case 'E':
{
for(j = 1; j <= k; ++j)
{
++x, A.x = x, A.y = y;
if(x || y)
res += search(A);
}
} break;
}
}
g << res << '\n';
f.close();
g.close();
return 0;
}