Cod sursa(job #1536273)

Utilizator preda.andreiPreda Andrei preda.andrei Data 25 noiembrie 2015 21:49:18
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#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;
}