Mai intai trebuie sa te autentifici.
Cod sursa(job #168518)
Utilizator | Data | 31 martie 2008 16:13:10 | |
---|---|---|---|
Problema | Zota & Chidil | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.4 kb |
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int dirs[13][2] = {
{0, 0},
{-1, 0},
{-2, 0},
{1, 0},
{2, 0},
{0, -1},
{0, -2},
{0, 1},
{0, 2},
{-1, -1},
{-1, 1},
{1, -1},
{1, 1},
};
vector<pii> vx,
vy;
bool ltx(const pii &a, const pii &b) {
if (a.first == b.first)
return a.second < b.second;
return a.first < b.first;
}
bool lty(const pii &a, const pii &b) {
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
int main(int argc, char *argv[]) {
FILE *fi = fopen("zc.in", "r");
int N, M;
fscanf(fi, "%d %d", &N, &M);
int x, y;
for (int i(0); i < N; ++i) {
fscanf(fi, "%d %d\n", &x, &y);
for (int d(0); d < 13; ++d)
if ((x + dirs[d][0] != 0) || (y + dirs[d][1] != 0))
vx.push_back(make_pair(x + dirs[d][0], y + dirs[d][1]));
}
vy = vx;
sort(vx.begin(), vx.end(), ltx);
sort(vy.begin(), vy.end(), lty);
vx.erase(unique(vx.begin(), vx.end()), vx.end());
vy.erase(unique(vy.begin(), vy.end()), vy.end());
/*for (int i(0); i < (int)vx.size(); ++i)
cout << i << "\t:\t" << vx[i].first << " " << vx[i].second << "\t|\t" << vy[i].first << " " << vy[i].second << endl;*/
char c;
int d;
x = y = 0;
int nx = 0,
ny = 0;
int tot = 0;
for (int i(0); i < M; ++i) {
fscanf(fi, "%c %d\n", &c, &d);
//cout << c << " " << d << endl;
if (c == 'N')
ny += d;
else if (c == 'S')
ny -= d;
else if (c == 'V')
nx -= d;
else
nx += d;
//cout << nx << " " << ny << endl;
if ((c == 'N') || (c == 'S')) {
/*cout << upper_bound(vx.begin(), vx.end(), make_pair(nx, ny), ltx) -
lower_bound(vx.begin(), vx.end(), make_pair(nx, y), ltx) << endl;*/
tot += upper_bound(vx.begin(), vx.end(), make_pair(nx, ny), ltx) -
lower_bound(vx.begin(), vx.end(), make_pair(nx, y), ltx);
if (binary_search(vx.begin(), vx.end(), make_pair(x, y), ltx))
--tot;
} else if ((c == 'V') || (c == 'E')) {
/*cout << upper_bound(vy.begin(), vy.end(), make_pair(nx, ny), lty) -
lower_bound(vy.begin(), vy.end(), make_pair(x, ny), lty) << endl;*/
tot += upper_bound(vy.begin(), vy.end(), make_pair(nx, ny), lty) -
lower_bound(vy.begin(), vy.end(), make_pair(x, ny), lty);
if (binary_search(vy.begin(), vy.end(), make_pair(x, y), lty))
--tot;
}
x = nx;
y = ny;
}
fclose(fi);
ofstream fout("zc.out");
fout << tot << endl;
fout.close();
return 0;
}