Pagini recente » Cod sursa (job #1942946) | Cod sursa (job #1888569) | Cod sursa (job #373863) | Cod sursa (job #1377048) | Cod sursa (job #614918)
Cod sursa(job #614918)
#include <cstdio>
#include <algorithm>
#define NMAX 100000
using namespace std;
struct point
{
int x, y;
} v1[NMAX], v2[NMAX];
int n, m;
bool cmp1(point a, point b) //sortez dupa x+y
{
if(a.x + a.y == b.x + b.y)
{
return a.x < b.x;
}
return a.x + a.y < b.x + b.y;
}
bool cmp2(point a, point b)
{
if(a.x - a.y == b.x - b.y)
{
return a.x < b.x;
}
return a.x - a.y < b.x - b.y;
}
int binary_search1(int s, int x)
{
int st, dr, m, sol;
st = 0;
dr = n-1;
sol = -1;
while(st <= dr)
{
m = (st + dr) / 2;
if(v1[m].x + v1[m].y < s || (v1[m].x + v1[m].y == s && v1[m].x <= x))
{
sol = m;
st = m + 1;
}
else
{
dr = m - 1;
}
}
return sol;
}
int binary_search2(int d, int x)
{
int st, dr, m, sol;
st = 0;
dr = n-1;
sol = -1;
while(st <= dr)
{
m = (st + dr) / 2;
if(v2[m].x - v2[m].y < d ||(v2[m].x - v2[m].y == d && v2[m].x <= x))
{
sol = m;
st = m + 1;
}
else
{
dr = m - 1;
}
}
return sol;
}
int main()
{
int i, x, y, r, dist;
freopen("grendizer.in", "r", stdin);
freopen("grendizer.out", "w", stdout);
scanf("%d %d", &n, &m);
for(i=0;i<n;++i)
{
scanf("%d %d", &v1[i].x, &v1[i].y);
v2[i] = v1[i];
}
sort(v1, v1+n, cmp1); //sortez dupa x + y
sort(v2, v2+n, cmp2); //sortez dupa x - y
for(i=0;i<m;++i)
{
scanf("%d %d %d", &x, &y, &r);
dist = 0;
dist += binary_search1(x+y-r, x) - binary_search1(x+y-r ,x-r-1);
dist += binary_search1(x+y+r, x+r) - binary_search1(x+y+r ,x-1);
dist += binary_search2(x-y-r, x-1) - binary_search2(x-y-r ,x-r);
dist += binary_search2(x-y+r, x+r-1) - binary_search2(x-y+r, x);
printf("%d\n", dist);
}
return 0;
}