Cod sursa(job #476438)

Utilizator andra23Laura Draghici andra23 Data 10 august 2010 23:30:48
Problema Zota & Chidil Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.98 kb
#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;
    } 
       
    sort(a+1, a+k+1, cmp1);
            
    punct ant = a[1];
    int dif, l;
    for (i = 1; i <= k; ){
        j = i+1;
        while (j <= k && a[j].x == a[i].x && a[j].y == a[i].y)
            j++;
        dif = j - (i+1);
        if (dif != 0){
            for (l = j; l <= k; l++)
                a[l-dif] = a[l];
            k = k-dif;   
        }
        i++; 
    }
    
    for (i = 1; i <= k; i++)
        b[i] = a[i];
    sort(b+1, b+k+1, cmp2);
    
    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;
}