Pagini recente » Cod sursa (job #2427909) | Cod sursa (job #24649) | Cod sursa (job #2773766) | Cod sursa (job #3128196) | Cod sursa (job #476412)
Cod sursa(job #476412)
#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct punct {
int x, y;
} a[1300010], b[1300010];
ofstream g;
int bsearch1(int k, int x, int y1, int y2){
int m;
int p1 = 0, p2 = k+1;
int p = 1, u = k;
while (p <= u){
m = (p+u)/2;
if ((a[m].x < x) || (a[m].x == x && a[m].y <= y1)){
p1 = m;
p = m+1;
}
else
u = m-1;
}
if ((p1 == 0) || (a[p1].x < x) || (a[p1].x == x && a[p1].y < y1))
p1++;
p = 1, u = k;
while (p <= u){
m = (p+u)/2;
if ((a[m].x > x) || (a[m].x == x && a[m].y >= y2)){
p2 = m;
u = m-1;
}
else
p = m+1;
}
if ((p2 == k+1) || (a[p2].x > x) || (a[p2].x == x && a[p2].y > y2))
p2--;
if (p2 >= p1)
return p2 - p1 + 1;
else
return 0;
}
int bsearch2(int k, int y, int x1, int x2){
int m;
int p1 = 0, p2 = k+1;
int p = 1, u = k;
while (p <= u){
m = (p+u)/2;
if ((b[m].y < y) || (b[m].y == y && b[m].x <= x1)){
p1 = m;
p = m+1;
}
else
u = m-1;
}
if ((p1 == 0) || (b[p1].y < y) || (b[p1].y == y && b[p1].x < x1))
p1++;
p = 1, u = k;
while (p <= u){
m = (p+u)/2;
if ((b[m].y > y) || (b[m].y == y && b[m].x >= x2)){
p2 = m;
u = m-1;
}
else
p = m+1;
}
if ((p2 == k+1) || (b[p2].y > y) || (b[p2].y == y && b[p2].x > x2))
p2--;
if (p2 >= p1)
return p2 - p1 + 1;
else
return 0;
}
int cmp1(punct a, punct b){
if (a.x < b.x)
return a.x < b.x;
else
if (a.x == b.x)
return a.y < b.y;
else
return b.x > a.x;
}
int cmp2(punct a, punct b){
if (a.y < b.y)
return a.y < b.y;
else
if (a.y == b.y)
return a.x < b.x;
else
return b.y > a.y;
}
int main(){
ifstream f("zc.in");
g.open("zc.out");
int m, n, i, j, k, x, y;
f>>n>>m;
k = 0;
for (i = 1; i <= n; i++){
f>>x>>y;
for ( j = y-2; j <= y+2; j++){
k++;
a[k].x = x;
a[k].y = j;
}
for ( j = y-1; j <= y+1; j++){
k++;
a[k].x = x-1;
a[k].y = j;
k++;
a[k].x = x+1;
a[k].y = j;
}
k++;
a[k].x = x-2;
a[k].y = y;
k++;
a[k].x = x+2;
a[k].y = y;
}
for (i = 1; i <= k; i++)
b[i] = a[i];
sort(a+1, a+k+1, cmp1);
sort(b+1, b+k+1, cmp2);
/*
for (i = 1; i <= k; i++)
g<<a[i].x<<" "<<a[i].y<<endl;
g<<endl;
for (i = 1; i <= k; i++)
g<<b[i].x<<" "<<b[i].y<<endl;
*/
int pas, praf = 0;
char c;
f.get();
x = 0; y = 0;
for (i = 1; i <= m; i++){
f.get(c);
f>>pas;
f.get();
if (c == 'N'){
praf = praf + bsearch1(k, x, y+1, y+pas);
y = y+pas;
}
else
if (c == 'S'){
praf = praf + bsearch1(k, x, y-pas, y-1);
y = y-pas;
}
else
if (c == 'E'){
praf = praf + bsearch2(k, y, x+1, x+pas);
x = x+pas;
}
else {
praf = praf + bsearch2(k, y, x-pas, x-1);
x = x-pas;
}
}
g<<praf<<'\n';
return 0;
}