首先统计[tex]Circle \rightarrow Square \rightarrow Circle[/tex]的情况([tex]Square \rightarrow Circle \rightarrow Square[/tex]可以对称算)。首先求出每个[tex]Circle[/tex]里面有几个[tex]Square[/tex]和每个[tex]Square[/tex]在几个[tex]Circle[/tex]里面(坐标变换+扫描线即可)。每个[tex]Square[/tex]对答案的贡献是[tex]- \frac{Count \times (Count-1)}{2}[/tex](因为下一步要重复计算)。此扫过所有的[tex]Circle[/tex](假设现在要求[tex]min[/tex]),[tex]Circle[i][/tex]对答案的贡献是[tex]\sum_{j=1}^{i-1}min(Count[i],Count[j])[/tex]。这个用树状数组就行了。[tex]max[/tex]同理。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#define MAXN 400010
#define MAXD 200005
struct dot{int x,y;} dots1[MAXN],dots2[MAXN]; //Dots1: Round Dots2: Square
struct ev{int pos,ind,type;} evs[2*MAXN];
int n,d,ev_num=0,bit[MAXN];
long long bit2[MAXN],cnt1[MAXN],cnt2[MAXN];
long long offset=0,ans1=0,ans2=0;
inline bool cmp1(const dot &lhs,const dot &rhs){return lhs.x<rhs.x||(lhs.x==rhs.x&&lhs.y<rhs.y);}
inline bool cmp2(const ev &lhs,const ev &rhs){return lhs.pos<rhs.pos||(lhs.pos==rhs.pos&&lhs.type<rhs.type);}
void edit(int pos,int x){if(!pos){bit[0]+=x;return;}while(pos<MAXN) bit[pos]+=x,pos+=pos&-pos;}
int query(int pos){if(pos<0) return 0;else if(!pos) return bit[0];int ans=0;while(pos) ans+=bit[pos],pos-=pos&-pos;return ans+bit[0];}
void edit2(int pos,int x){if(!pos){bit2[0]+=x;return;}while(pos<MAXN) bit2[pos]+=x,pos+=pos&-pos;}
long long query2(int pos){if(pos<0) return 0;else if(!pos) return bit2[0];long long ans=0;while(pos) ans+=bit2[pos],pos-=pos&-pos;return ans+bit2[0];}
int main()
{
    //freopen("3001.txt","r",stdin);
    scanf("%d%d",&n,&d);
    for(int i=0,tmp1,tmp2;i<n;i++) scanf("%d%d",&tmp1,&tmp2),dots1[i]=(dot){tmp1+tmp2,tmp1-tmp2+MAXD};
    for(int i=0,tmp1,tmp2;i<n;i++) scanf("%d%d",&tmp1,&tmp2),dots2[i]=(dot){tmp1+tmp2,tmp1-tmp2+MAXD};
    for(int i=0;i<n;i++) evs[ev_num++]=(ev){dots1[i].x-d-1,i,1},evs[ev_num++]=(ev){dots1[i].x+d,i,2};
    for(int i=0;i<n;i++) evs[ev_num++]=(ev){dots2[i].x,i,0};
    std::stable_sort(evs,evs+ev_num,cmp2);
    for(int i=0;i<ev_num;i++)
    {
        if(evs[i].type==0) edit(dots2[evs[i].ind].y,1);
        else if(evs[i].type==1) cnt1[evs[i].ind]-=query(dots1[evs[i].ind].y+d)-query(dots1[evs[i].ind].y-d-1);
        else if(evs[i].type==2) cnt1[evs[i].ind]+=query(dots1[evs[i].ind].y+d)-query(dots1[evs[i].ind].y-d-1);
    }
    ev_num=0,memset(bit,0,sizeof(bit));
    for(int i=0;i<n;i++) evs[ev_num++] =(ev){dots2[i].x-d-1,i,1},evs[ev_num++]=(ev){dots2[i].x+d,i,2};
    for(int i=0;i<n;i++) evs[ev_num++]=(ev){dots1[i].x,i,0};
    std::stable_sort(evs,evs+ev_num,cmp2);
    for(int i=0;i<ev_num;i++)
    {
        if(evs[i].type==0) edit(dots1[evs[i].ind].y,1);
        else if(evs[i].type==1) cnt2[evs[i].ind]-=query(dots2[evs[i].ind].y+d)-query(dots2[evs[i].ind].y-d-1);
        else if(evs[i].type==2) cnt2[evs[i].ind]+=query(dots2[evs[i].ind].y+d)-query(dots2[evs[i].ind].y-d-1);
    }
    for(int i=0;i<n;i++) offset+=((long long)cnt1[i])*(cnt1[i]-1)>>1;
    for(int i=0;i<n;i++) offset+=((long long)cnt2[i])*(cnt2[i]-1)>>1;
    memset(bit,0,sizeof(bit));
    for(int i=0;i<n;i++)
    {
        ans1+=query2(cnt1[i]-1)+(query(MAXN-1)-query(cnt1[i]-1))*cnt1[i];
        ans2+=query2(MAXN-1)-query2(cnt1[i]-1)+query(cnt1[i]-1)*cnt1[i];
        edit(cnt1[i],1),edit2(cnt1[i],cnt1[i]);
    }
    memset(bit,0,sizeof(bit)),memset(bit2,0,sizeof(bit2));
    for(int i=0;i<n;i++)
    {
        ans1+=query2(cnt2[i]-1)+(query(MAXN-1)-query(cnt2[i]-1))*cnt2[i];
        ans2+=query2(MAXN-1)-query2(cnt2[i]-1)+query(cnt2[i]-1)*cnt2[i];
        edit(cnt2[i],1),edit2(cnt2[i],cnt2[i]);
    }
    printf("%lld %lld\n",ans1-offset,ans2-offset);
    return 0;
}