题目描述
给定\(n\)个点，找出三个点使得这三个点两两之间的曼哈顿距离为偶数\(d\)
\[n\le 300000 \]题解
与一个点的曼哈顿距离为\(d\)的点是一个斜\(45°\)的正方形
设这个点坐标为\((x,y)\)
考虑另外两个点可能在哪些位置，
如果另外两个点在正方形的同一条边上，那么这两个点的横纵坐标的差的绝对值一定都等于\(d/2\)，即满足\(|x_1-x_2|=d/2,|y_1-y_2|=d/2\)
如果不在同一条边上，那么一定有一个点与\((x,y)\)满足\(|x_1-x|=d/2,|y_1-y|=d/2\)
也就是说如果可以找到三个点满足两两之间的曼哈顿距离为偶数\(d\)，那么这三个点中一定存在两个点满足\(|x_1-x_2|=d/2,|y_1-y_2|=d/2\)
那么做法就很简单了，枚举其中一个点，判断是否存在另一个点满足\(|x_1-x_2|=d/2,|y_1-y_2|=d/2\)，这个可以用\(map\)判断，然后就是找到一个在这两个点的正方形的交集上的点，交集其实就是两条线段，可以预处理排序后用二分判断，具体可以看代码
时间复杂度\(O(n\log n)\)
\(\text{code}\)
#include<cstdio>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int N=1e6+1000,M=4e5,inf=1e9+10;
int n,d,a[N+10],b[N+10];
struct node
{
int x,y;
}p[N+10];
map<pair<int,int>,int> t;
vector<int> t1[N+10],t2[N+10];
bool cmp(int a,int b){return p[a].x<p[b].x;}
int check(int x1,int y1,int x2,int y2)
{
int c=0;
if(y1-x1==y2-x2)
{
c=y1-x1+M;
if(t1[c].size()==0) return false;
int l=0,r=t1[c].size()-1,ans=-1;
for(int mid;l<=r;)
{
mid=l+r>>1;
if(p[t1[c][mid]].x<=x2) ans=mid,l=mid+1;
else r=mid-1;
}
if(ans==-1) return 0;
if(p[t1[c][ans]].x>=x1) return t1[c][ans];
else return 0;
}
else
{
c=x1+y1+M;
if(t2[c].size()==0) return false;
int l=0,r=t2[c].size()-1,ans=-1;
for(int mid;l<=r;)
{
mid=l+r>>1;
if(p[t2[c][mid]].x<=x2) ans=mid,l=mid+1;
else r=mid-1;
}
if(ans==-1) return 0;
if(p[t2[c][ans]].x>=x1) return t2[c][ans];
else return 0;
}
return 0;
}
void solve()
{
for(int i=1,tmp;i<=n;i++)
{
int x=p[i].x,y=p[i].y,k=d>>1;
if(t.find({x-k,y-k})!=t.end())
{
tmp=check(x-d,y,x-k,y+k);
if(tmp)
{
// puts("fuc");
// printf("%d %d %d\n",x,y,k);
// printf("%d %d\n",p[t[{x-k,y-k}]].x,p[t[{x-k,y-k}]].y);
printf("%d %d %d",i,t[{x-k,y-k}],tmp);
return;
}
tmp=check(x,y-d,x+k,y-k);
if(tmp)
{
printf("%d %d %d",i,t[{x-k,y-k}],tmp);
return;
}
}
if(t.find({x-k,y+k})!=t.end())
{
tmp=check(x-d,y,x-k,y-k);
if(tmp)
{
printf("%d %d %d",i,t[{x-k,y+k}],tmp);
return;
}
tmp=check(x,y+d,x+k,y+k);
if(tmp)
{
printf("%d %d %d",i,t[{x-k,y+k}],tmp);
return;
}
}
}
printf("0 0 0");
}
int main()
{
// freopen("e.in","r",stdin);
int T;
scanf("%d",&T);
for(;T--;)
{
scanf("%d %d",&n,&d);
for(int i=1;i<=n;i++) scanf("%d %d",&p[i].x,&p[i].y),t[{p[i].x,p[i].y}]=i;
for(int i=1;i<=n;i++)
{
t1[p[i].y-p[i].x+M].push_back(i),a[i]=p[i].y-p[i].x+M;
t2[p[i].y+p[i].x+M].push_back(i),b[i]=p[i].y+p[i].x+M;
}
sort(a+1,a+1+n),sort(b+1,b+1+n);
for(int i=1;i<=n;i++)
if(a[i]!=a[i-1])
sort(t1[a[i]].begin(),t1[a[i]].end(),cmp);
for(int i=1;i<=n;i++)
if(b[i]!=b[i-1])
sort(t2[b[i]].begin(),t2[b[i]].end(),cmp);
solve(),puts("");
for(int i=1;i<=n;i++) t1[a[i]].clear();
for(int i=1;i<=n;i++) t2[b[i]].clear();
t.clear();
}
return 0;
}