Pagini recente » Cod sursa (job #2789604) | Cod sursa (job #2464206) | Cod sursa (job #919384) | Cod sursa (job #3254431) | Cod sursa (job #685778)
Cod sursa(job #685778)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
using namespace std;
struct XY
{
int x,y;
};
vector<XY> v;
void AddCpacana(XY xy);
bool cautare(XY xy);
bool compare(XY i1,XY i2)
{
if(i1.x != i2.x)
return (i1.x < i2.x);
return (i1.y < i2.y);
}
int main()
{
int n,m,dir,cel = 0;
XY poz;
poz.x = 0,poz.y = 0;
char c;
ifstream fin("zc.in");
XY xy;
fin >> n >> m;
for(int i = 1;i <= n;++i )
{
fin>>xy.x>>xy.y;
AddCpacana(xy);
}
/*
for(int i = 0; i < v.size();++i)
{
cout << v[i].x <<' '<<v[i].y<<'\n';
}
cout << "\n\n\n";
*/
sort(v.begin(),v.end(),compare);
/*
for(int i = 0; i < v.size();++i)
{
cout << v[i].x <<' '<<v[i].y<<'\n';
}
cout << "\n\n";
*/
for(int i = 1; i <= m;++i)
{
fin >> c >> dir;
//cout << c <<" "<<dir <<'\n';
int dx,dy;
if( c == 'N')
dx = 0 , dy = 1;
else if(c == 'E')
dx = 1 , dy = 0;
else if(c == 'V')
dx = -1,dy = 0;
else
dx = 0, dy = -1;
for(int k = 1; k <= dir ; ++k)
{
poz.x += dx,poz.y += dy;
// cout << poz.x << " " << poz.y << '\n';
if(cautare(poz) == true)
cel++;
}
}
fin.close();
ofstream fout("zc.out");
fout<<cel;
fout.close();
return 0;
}
bool cautare(XY xy)
{
int low = 0 , high = v.size() - 1,mid;
while(low <= high)
{
mid = (low + high) / 2;
if(v[mid].x == xy.x && v[mid].y == xy.y)
return true;
else if((v[mid].x > xy.x) || (v[mid].x == xy.x && v[mid].y > xy.y))
high = mid -1;
else
low = mid + 1;
}
return false;
}
void AddCpacana(XY xy)
{
short dx[]={1,0,-1,0,2,0,-2,0,1,-1,1,-1};
short dy[]={0,1,0,-1,0,2,0,-2,1,-1,-1,1};
int n = sizeof(dx)/sizeof(short);
XY aux;
v.push_back(xy);
for(int k = 0; k < n;++k)
{
aux.x = xy.x + dx[k],aux.y = xy.y + dy[k];
v.push_back(aux);
}
}