题意

平面上 个点，问取三个点的方案数使得三个点的三个曼哈顿距离排序后第二个为素数。

思路

据说这道题可以转成切比雪夫距离然后有很优雅的 做法，但是我不会。

我们考虑 怎么做，由于“素数”是个极度奇怪的限制，所以我们不妨枚举这条中间的边的长度为 ，然后就可以得到两个点。接下来只需要在一个端点的边中选一条长度小于等于 的边，另一个选取一条长度大于等于 的边，只要这两条边具有相同的顶点就可以构成一个合法方案了。

这样只要每个点的边是按照长度排序的，就可以变成两个范围内的一些数据取并的问题的了。

由于取并是一个难以维护的操作，我们直接选择 Bitset。

由于 的空间是无法接受的，所以我们不能对于排序之后的边的前后缀维护 Bitset，只能选择通过对全局边进行排序，然后按照顺序枚举以将对 Bitset 的维护转换成类似于指针扫描的形式。

需要注意的是，对于三条边中有两条边或三条边相等的情况，我们会算重，所以需要对于等于 的边单独开一个 Bitset 将这些情况处理出来，再进行修正。

实现

细节不少。

我们注意到在计算等于 的边的时候我们可能直接计算到我们枚举的这条边，所以我们再用一个 Bitset 将两个端点去掉。

首先，如果我们直接的将小于等于大于三种 Bitset 按照如上的方式操作计算答案，是无法通过此题的，因为计算有两条边相等的代码看起来像这样：

(((pre[i.x]&mid[i.y])|(mid[i.x]&suf[i.y])|(pre[i.y]&mid[i.x])|(mid[i.y]&suf[i.x]))&none).count()

这将带来一个巨大的常数。

所以对于有两条边相等的情况我们需要特殊处理。

我们可以枚举一个点，然后扫描其每一组相同长度的边，然后进行统计。

因为有两条边的长度一样，所以这个长度一定会是中间的那条边的长度。

问题在于我们会将三条边相同的情况计算三次，所以我们需要按照上面的方法将三边相同的情况计算出来，然后容斥掉。

另外，真正的优化（好像可以只使用这个优化就能过）是我们对于全局边排序时使用计数排序（因为值域只有 ），然后按照这个顺序加边，这样就可以避免多余的排序，在极限数据上可以直接优化掉一秒多。

CODE

#include<cstdio>
#include<bitset>
#include<vector>
#include<deque>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2010,FSIZE=1<<24,MX=200010;
using uni=unsigned;
using ll=long long;
using db=double;
int x[N],y[N],w[MX],pr[MX/10];
bool no[MX];
struct line{int d,x;};
struct line2{int d,x,y;};
bitset<N> pre[N],mid[N],suf[N],none;
deque<line> a[N];
deque<line>::iterator l[N],r[N];
vector<line2> all;
line2 tmp[N*N];
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    bool f=1;
    for(;48>*InF||*InF>57;f^=*InF++=='-');
    for(x=0;47<*InF&&*InF<58;x=x*10+(*InF++^48));
    x=f?x:-x;
}
int dis(int i,int j){
    return(abs(x[i]-x[j])+abs(y[i]-y[j]));
}
void get(int x,int d){
    for(;r[x]!=a[x].end()&&r[x]->d<=d;++r[x]){
        mid[x][r[x]->x]=1;
        suf[x][r[x]->x]=0;
    }
    for(;l[x]!=a[x].end()&&l[x]->d<d;++l[x]){
        pre[x][l[x]->x]=1;
        mid[x][l[x]->x]=0;
    }
}
template<class T>void Sort(T beg,T end){
    memset(w,0,sizeof(w));
    for(auto i=beg;i<end;++w[i++->d]);
    for(int *i=w,*r=w+MX;i<r;++i) *(i+1)+=*i;
    for(auto i=beg;i<end;++i) tmp[--w[i->d]]=*i;
    memcpy(&*beg,tmp,(end-beg)*sizeof(line2));
}
void work(){
    int n,m;
    ll ans1=0,ans3=0;
    read(n);read(m);
    all.clear();
    for(int i=1;i<=n;++i){
        read(x[i]);read(y[i]);
        a[i].clear();
    }
    for(int i=1;i<n;++i)
        for(int j=i+1;j<=n;++j)
            all.push_back({dis(i,j),i,j});
    Sort(all.begin(),all.end());
    for(auto i:all){
        a[i.x].push_back({i.d,i.y});
        a[i.y].push_back({i.d,i.x});
    }
    for(int i=1;i<=n;++i){
        pre[i].reset();
        mid[i].reset();
        suf[i].reset();
        l[i]=r[i]=a[i].begin();
        for(auto j:a[i]) suf[i][j.x]=1;
    }
    none.set();
    for(auto i:all)
        if(!no[i.d]){
            get(i.x,i.d);
            get(i.y,i.d);
            none[i.x]=none[i.y]=0;
            ans1+=(((pre[i.x]&suf[i.y])|(pre[i.y]&suf[i.x]))&none).count();
            ans3+=(mid[i.x]&mid[i.y]&none).count();
            none[i.x]=none[i.y]=1;
        }
    for(int i=1;i<=n;++i){
        auto j=a[i].begin(),k=j;
        for(;j!=a[i].end();j=k){
            for(k=j;j->d==k->d&&k<a[i].end();++k);
            if(!no[j->d]) ans1+=(k-j)*(k-j-1)>>1;
            if(k==a[i].end()) break;
        }
    }
    printf("%lld\n",ans1-(ans3/3)*2);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    int t;
    no[1]=1;
    for(int i=2,cnt=0;i<MX;++i){
        if(!no[i]) pr[cnt++]=i;
        for(int j=0;j<cnt&&i*pr[j]<MX;++j){
            no[i*pr[j]]=1;
            if(!(i%pr[j])) break;
        }
    }
    for(read(t);t--;work());
    fclose(stdin);
    fclose(stdout);
    return(0);
}