Pagini recente » Cod sursa (job #3200230) | Cod sursa (job #1723968) | Cod sursa (job #1444568) | Cod sursa (job #2939740) | Cod sursa (job #476869)
Cod sursa(job #476869)
#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>>a[i].x>>a[i].y;
b[i] = a[i];
}
sort(a+1, a+n+1, cmp1);
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;
}