Pagini recente » Cod sursa (job #2030016) | Cod sursa (job #2261582) | Cod sursa (job #1360272) | Cod sursa (job #1499771) | Cod sursa (job #1536273)
#include <iostream>
#include <stdio.h>
using namespace std;
struct Punct{
int x, y;
};
const short int modLin[4]={1, 0, -1, 0};
const short int modCol[4]={0, 1, 0, -1};
Punct cap[100001];
int indiceDir(char ch){
if(ch=='N')
return 0;
if(ch=='E')
return 1;
if(ch=='S')
return 2;
return 3;
}
bool cmpMic(Punct p1, Punct p2){
if(p1.x==p2.x)
return p1.y<p2.y;
return p1.x<p2.x;
}
void sortare(int n){
Punct paux;
int x;
for(int i=1; i<n; ++i){
x=i;
for(int j=i+1; j<=n; ++j)
if(cmpMic(cap[j], cap[x]))
x=j;
if(i!=x){
paux=cap[i];
cap[i]=cap[x];
cap[x]=paux;
}
}
}
int abs(int a){
if(a>=0)
return a;
return -a;
}
bool inRaza(Punct p1, Punct p2){
return abs(p1.x-p2.x)+abs(p1.y-p2.y)<=2;
}
bool capcana(int x, int y, int n){
Punct pr={x, y};
int st, dr, mij;
st=1;
dr=n;
while(st<=dr){
mij=st+(dr-st)/2;
if(inRaza(pr, cap[mij]))
return true;
if(cmpMic(cap[mij], pr))
st=mij+1;
else dr=mij-1;
}
return false;
}
int main()
{
FILE *fin=fopen("zc.in", "r");
FILE *fout=fopen("zc.out", "w");
int n, m, praf=0, k, rx, ry, ind;
char ch;
fscanf(fin, "%d%d", &n, &m);
for(int i=1; i<=n; ++i)
fscanf(fin, "%d%d", &cap[i].y, &cap[i].x);
sortare(n);
rx=ry=0;
for(int i=1; i<=m; ++i){
fscanf(fin, "\n%c %d", &ch, &k);
ind=indiceDir(ch);
for(int j=1; j<=k; ++j){
rx+=modLin[ind];
ry+=modCol[ind];
if(!(rx==0 && ry==0) && capcana(rx, ry, n))
praf++;
}
}
fprintf(fout, "%d", praf);
return 0;
}