Pagini recente » Cod sursa (job #21187) | Cod sursa (job #450883) | Cod sursa (job #1885855) | Cod sursa (job #1046724) | Cod sursa (job #476863)
Cod sursa(job #476863)
#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;
}