Cod sursa(job #476863)

Utilizator andra23Laura Draghici andra23 Data 12 august 2010 15:21:02
Problema Grendizer Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.87 kb
#include<iostream>
#include<fstream>
#include<algorithm>

using namespace std;

struct punct{
    int x, y;
} a[100010], b[100010], c[100010];
int n;

int cmp1(punct a, punct b){
    if ((a.y-a.x) == (b.y-b.x))
        return a.x < b.x;
    else 
        return (a.y-a.x) < (b.y-b.x);    
}

int cmp2(punct a, punct b){
    if ((a.y+a.x) == (b.y+b.x))
        return a.x < b.x;
    else 
        return (a.y+a.x) < (b.y+b.x);    
}

int bs1(int x, int y){
    int m, pos = n+1;
    int p = 1, u = n;
    while (p <= u){
        m = (p+u)/2;
        if ((a[m].y - a[m].x > y-x) || (a[m].y - a[m].x == y-x && a[m].x >= x)){
            pos = m;
            u = m-1;
        }
        else
            p = m+1; 
    }
    return pos;
}

int bs2(int x, int y){
    int m, pos = n+1;
    int p = 1, u = n;
    while (p <= u){
        m = (p+u)/2;
        if ((b[m].y + b[m].x > y+x) || (b[m].y + b[m].x == y+x && b[m].x >= x)){
            pos = m;
            u = m-1;
        }
        else
            p = m+1; 
    }
    return pos;
}

int main(){
    ifstream f("grendizer.in");
    ofstream g("grendizer.out");
    int m, i, j=0, x, y, r;
    long long rez;
    
    f>>n>>m;
    for (i = 1; i <= n; i++){
        f>>c[i].x>>c[i].y;
    }
    
    sort(c+1, c+n+1, cmp1);
    
    i = 1;
    while (i <= n){
        j++;
        a[j] = c[i];
        while (c[i].x == a[j].x && c[i].y == a[j].y)
            i++; 
    }
    
    n = j;
    for ( i = 1; i <= n; i++)
        b[i] = a[i];
        
    sort(b+1, b+n+1, cmp2);
    
    for (i = 1; i <= m; i++){
        f>>x>>y>>r;
        rez = bs1(x+r+1, y+1) - bs1(x, y-r);
        rez = rez + bs2(x+r, y) - bs2(x, y+r);
        rez = rez + bs1(x, y+r) - bs1(x-r+1, y+1);
        rez = rez + bs2(x, y-r) - bs2(x-r, y);
        g<<rez<<'\n';
    }
    
    return 0;
}