Pagini recente » Monitorul de evaluare | Cod sursa (job #2800525) | Cod sursa (job #1597848) | Cod sursa (job #1520383) | Cod sursa (job #2580614)
#include <fstream>
#include <algorithm>
#define nmax 100002
using namespace std;
ifstream fin("grendizer.in");
ofstream fout("grendizer.out");
int n,m;
int x,y,r;
struct pct
{
int x,y;
}v1[nmax],v2[nmax];
bool cmpPlus(pct a,pct b)
{
return (a.x+a.y<b.x+b.y || (a.x+a.y==b.x+b.y && a.y<b.y));
}
bool cmpMinus(pct a,pct b)
{
return (a.x-a.y<b.x-b.y || (a.x-a.y==b.x-b.y && a.y<b.y));
}
int binPlus(int r,int a,int b)
{
int st=1,dr=n,sol1=-1,sol2=-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(v1[mij].x+v1[mij].y<r)
st=mij+1;
else if(v1[mij].x+v1[mij].y>r)
dr=mij-1;
else
{
if(v1[mij].y<a)st=mij+1;
else
{
sol1=mij;
dr=mij-1;
}
}
}
st=1,dr=n;
while(st<=dr)
{
int mij=(st+dr)/2;
if(v1[mij].x+v1[mij].y<r)
st=mij+1;
else if(v1[mij].x+v1[mij].y>r)
dr=mij-1;
else
{
if(v1[mij].y>b)dr=mij-1;
else
{
sol2=mij;
st=mij+1;
}
}
}
if(sol1>0 && sol2>0)
return sol2-sol1+1;
return 0;
}
int binMinus(int r,int a,int b)
{
int st=1,dr=n,sol1=-1,sol2=-1;
while(st<=dr)
{
int mij=(st+dr)/2;
if(v2[mij].x-v2[mij].y<r)
st=mij+1;
else if(v2[mij].x-v2[mij].y>r)
dr=mij-1;
else
{
if(v2[mij].y<a)st=mij+1;
else
{
sol1=mij;
dr=mij-1;
}
}
}
st=1,dr=n;
while(st<=dr)
{
int mij=(st+dr)/2;
if(v2[mij].x-v2[mij].y<r)
st=mij+1;
else if(v2[mij].x-v2[mij].y>r)
dr=mij-1;
else
{
if(v2[mij].y>b)dr=mij-1;
else
{
sol2=mij;
st=mij+1;
}
}
}
if(sol1>0 && sol2>0)
return sol2-sol1+1;
return 0;
}
int main()
{
fin>>n>>m;
for(int i=1;i<=n;i++)
{
fin>>x>>y;
v1[i].x=v2[i].x=x;
v1[i].y=v2[i].y=y;
}
sort(v1+1,v1+n+1,cmpPlus);
sort(v2+1,v2+n+1,cmpMinus);
for(int i=1;i<=m;i++)
{
fin>>x>>y>>r;
int ans=0;
ans+=binPlus(x+y-r,y-r,y);
ans+=binPlus(x+y+r,y,y+r);
ans+=binMinus(x-y+r,y-r+1,y-1);
ans+=binMinus(x-y-r,y+1,y+r-1);
fout<<ans<<"\n";
}
return 0;
}