Cod sursa(job #1513027)

Utilizator preda.andreiPreda Andrei preda.andrei Data 28 octombrie 2015 21:48:53
Problema Zota & Chidil Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.7 kb
#include <iostream>
#include <stdio.h>

using namespace std;

const short int modLin[4]={1, 0, -1, 0};
const short int modCol[4]={0, 1, 0, -1};

int capx[100001];
int capy[100001];

int modul(int a){
    if(a>=0)
        return a;
    return -a;
}

void inter(int &a, int &b){
    int c=a;
    a=b;
    b=c;
}

bool inRaza(int cx, int cy, int x, int y){
    if(modul(cx-x)+modul(cy-y)<=2)
        return true;
    return false;
}

int comp(int x1, int y1, int x2, int y2){
    if(x1<x2)
        return -1;
    if(x1>x2)
        return 1;
    if(y1<y2)
        return -1;
    if(y1>y2)
        return 1;
    return 0;
}

int partitionare(int st, int dr){
    int i, j, xx, xy;

    xx=capx[st];
    xy=capy[st];
    i=st;
    j=dr;
    while(i<j){
        while(i<j && comp(capx[j], capy[j], xx, xy)>0)
            j--;
        capx[i]=capx[j];
        capy[i]=capy[j];
        while(i<j && comp(capx[i], capy[i], xx, xy)<0)
            i++;
        capx[j]=capx[i];
        capy[j]=capy[i];
    }

    capx[i]=xx;
    capy[i]=xy;
    return i;
}

void sortare(int st, int dr){
    if(st<dr){
        int poz=partitionare(st, dr);
        sortare(st, poz-1);
        sortare(poz+1, dr);
    }
}

bool pericol(int x, int y, int n){
    int st, dr, mij, poz=0;

    st=1;
    dr=n;
    while(st<=dr){
        mij=st+(dr-st)/2;
        if(capx[mij]>=x-2 && capx[mij]<=x+2){
            poz=mij;
            dr=mij-1;
        }
        else if(capx[mij]<x-2)
            st=mij+1;
        else dr=mij-1;
    }

    if(poz==0)
        return false;

    while(poz<=n && capx[poz]<=x+2)
        if(inRaza(capx[poz], capy[poz], x, y)){
            //printf("%d %d in raza lui %d %d\n", x, y, capx[poz], capy[poz]);
            return true;
        }
        else poz++;

    return false;
}

int main()
{
    FILE *fin=fopen("zc.in", "r");
    FILE *fout=fopen("zc.out", "w");

    int n, m, praf, cox, coy, ind, k;
    char ch;

    fscanf(fin, "%d%d", &n, &m);
    for(int i=1; i<=n; ++i)
        fscanf(fin, "%d%d", &capy[i], &capx[i]);

    sortare(1, n);

    cox=coy=praf=0;
    fscanf(fin, "\n");
    for(int i=1; i<=m; ++i){
        fscanf(fin, "%c %d\n", &ch, &k);
        if(ch=='N')
            ind=0;
        else if(ch=='E')
            ind=1;
        else if(ch=='S')
            ind=2;
        else ind=3;

        for(int j=1; j<=k; ++j){
            cox+=modLin[ind];
            coy+=modCol[ind];
            if(!(cox==0 && coy==0) && pericol(cox, coy, n)){
                praf++;
                //fprintf(fout, "%d %d\n", cox, coy);
            }
        }
    }

    fprintf(fout, "%d", praf);
    return 0;
}