Pagini recente » Cod sursa (job #82334) | Cod sursa (job #971064) | Cod sursa (job #758113) | Cod sursa (job #771595) | Cod sursa (job #498844)
Cod sursa(job #498844)
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
void make_arrays();
bool mycrt1(const pair<int, int>& p1, const pair<int, int>& p2)
{
if (p1.first != p2.first)
return p1.first <= p2.first;
return p1.second <= p2.second;
}
bool mycrt2(const pair<int, int>& p1, const pair<int, int>& p2)
{
if (p1.second != p2.second)
return p1.second <= p2.second;
return p1.first <= p2.first;
}
int N, M;
vector<pair<int, int> > S1, S2;
int tot;
int main()
{
ifstream fin("zc.in");
ofstream fout("zc.out");
fin >> N >> M;
for (int i = 1, c1, c2; i <= N; ++i)
{
fin >> c1 >> c2;
int aux = 0, chg = 0;
for (int j = c1 - 2; j <= c1 + 2; ++j)
{
for (int k = c2 - aux; k <= c2 + aux; ++k)
if (!(j == 0 && k == 0))
S1.push_back(make_pair(j, k));
if (chg == 0) ++aux;
else --aux;
if (aux == 2) chg = true;
}
}
make_arrays();
char ch;
int dm;
int posx = 0, posy = 0;
int rstep;
for (rstep = 1; (rstep << 1) <= S1.size(); rstep <<= 1);
for (int i = 1; i <= M; ++i)
{
fin >> ch >> dm;
int step, j1, j2;
switch (ch)
{
case 'N':
step = rstep;
for (j1 = -1; step; step >>= 1)
if (j1 + step < S1.size())
{
if (S1[j1 + step].first < posx)
j1 += step;
else if (S1[j1 + step].first == posx && S1[j1 + step].second < posy)
j1 += step;
}
step = rstep;
for (j2 = -1; step; step >>= 1)
if (j2 + step < S1.size())
{
if (S1[j2 + step].first < posx)
j2 += step;
else if (S1[j2 + step].first == posx && S1[j2 + step].second <= posy + dm)
j2 += step;
}
tot += j2 - j1;
posy += dm;
break;
case 'S':
step = rstep;
for (j1 = -1; step; step >>= 1)
if (j1 + step < S1.size())
{
if (S1[j1 + step].first < posx)
j1 += step;
else if (S1[j1 + step].first == posx && S1[j1 + step].second < posy - dm)
j1 += step;
}
step = rstep;
for (j2 = -1; step; step >>= 1)
if (j2 + step < S1.size())
{
if (S1[j2 + step].first < posx)
j2 += step;
else if (S1[j2 + step].first == posx && S1[j2 + step].second <= posy)
j2 += step;
}
tot += j2 - j1;
posy -= dm;
break;
case 'E':
step = rstep;
for (j1 = -1; step; step >>= 1)
if (j1 + step < S2.size())
{
if (S2[j1 + step].second < posy)
j1 += step;
else if (S2[j1 + step].second == posy && S2[j1 + step].first < posx)
j1 += step;
}
step = rstep;
for (j2 = -1; step; step >>= 1)
if (j2 + step < S2.size())
{
if (S2[j2 + step].second < posy)
j2 += step;
else if (S2[j2 + step].second == posy && S2[j2 + step].first <= posx + dm)
j2 += step;
}
tot += j2 - j1;
posx += dm;
break;
case 'V':
step = rstep;
for (j1 = -1; step; step >>= 1)
if (j1 + step < S2.size())
{
if (S2[j1 + step].second < posy)
j1 += step;
else if (S2[j1 + step].second == posy && S2[j1 + step].first < posx - dm)
j1 += step;
}
step = rstep;
for (j2 = -1; step; step >>= 1)
if (j2 + step < S2.size())
{
if (S2[j2 + step].second < posy)
j2 += step;
else if (S2[j2 + step].second == posy && S2[j2 + step].first <= posx)
j2 += step;
}
tot += j2 - j1;
posx -= dm;
break;
}
}
fout << tot;
fin.close();
fout.close();
}
void make_arrays()
{
S2 = S1;
sort(S1.begin(), S1.end(), mycrt1);
sort(S2.begin(), S2.end(), mycrt2);
vector<pair<int, int> >::iterator it;
it = unique(S1.begin(), S1.end());
S1.resize(it - S1.begin());
it = unique(S2.begin(), S2.end());
S2.resize(it - S2.begin());
}