[DS记录]AT2160 [ARC065C] へんなコンパス / Manhattan Compass
command_block
2021-05-17 09:09:46
**题意** ： （这翻译都是些啥，看不懂 qwq）
给出平面上的 $n$ 个点。
记点 $p_i,p_j$ 之间的曼哈顿距离为 $d(i,j)=|x_i-x_j|+|y_i-y_j|$。
有两个人（不区分），初始时分别在点 $p_a,p_b$。
当两人在点 $u,v$ 时，若存在点 $t$ 满足 $d(u,v)=d(u,t)$ ，则在 $v$ 的人可以移动到 $t$。
求两人能达到的不同状态（位置无序对）总数。
$n\leq 10^5$ ，时限$\texttt{3s}$。
------------
记 $L=d(p_a,p_b)$ ，不难发现，在旅途中 $d(u,v)$ 是不会变化的，一直为 $L$。
若某个人能到达点 $u$ ，则对于所有 $d(u,v)=L$ 的 $v$ ，无序对 $(u,v)$ 都是可达的。
于是，只需判定每个点能否被到达。
对于某个已经被到达的点 $u$，检查所有 $d(u,v)=L$ 的 $v$ ，把他们也更新为可达点。
这可以用队列实现，并用 `std::set` 维护点（转切比雪夫距离更方便）。
每个点只会被删除一次，故复杂度为 $O(n\log n)$。
写起来没啥难点，就是有点啰嗦。
```cpp
#include<algorithm>
#include<cstdio>
#include<vector>
#include<queue>
#include<set>
#define Pr pair<int,int>
#define fir first
#define sec second
#define mp make_pair
#define pb push_back
#define ll long long
#define itor set<Pr>::iterator
#define MaxN 100500
using namespace std;
const int INF=2000000100;
int abs(int x){return (x<0) ? -x : x;}
set<Pr> sx[MaxN],sy[MaxN];
vector<int> tx[MaxN],ty[MaxN];
int n,x[MaxN],y[MaxN],ax[MaxN],ay[MaxN],d[MaxN];
bool vis[MaxN];
queue<int> q;
void del(itor itl,itor itr,set<Pr> &s){
for (itor sav;itl!=itr;){
q.push(itl->sec);
sav=itl;itl++;
s.erase(sav);
}
}
int main()
{
int u,v;
scanf("%d%d%d",&n,&u,&v);
for (int i=1,x0,y0;i<=n;i++){
scanf("%d%d",&x0,&y0);
ax[i]=x[i]=x0-y0;
ay[i]=y[i]=x0+y0;
}sort(ax+1,ax+n+1);sort(ay+1,ay+n+1);
for (int i=1;i<=n;i++){
int x0=lower_bound(ax+1,ax+n+1,x[i])-ax
,y0=lower_bound(ay+1,ay+n+1,y[i])-ay;
tx[x0].pb(y[i]);ty[y0].pb(x[i]);
sx[x0].insert(mp(y[i],i));sy[y0].insert(mp(x[i],i));
}
for (int i=1;i<=n;i++){
sort(tx[i].begin(),tx[i].end());
sort(ty[i].begin(),ty[i].end());
}
int L=max(abs(x[u]-x[v]),abs(y[u]-y[v]));
for (int i=1,l,r;i<=n;i++){
if ((ll)x[i]-L>-INF){
int to=lower_bound(ax+1,ax+n+1,x[i]-L)-ax;
if (ax[to]==x[i]-L){
l=lower_bound(tx[to].begin(),tx[to].end(),max(-INF,y[i]-L))-tx[to].begin();
r=upper_bound(tx[to].begin(),tx[to].end(),min(INF,y[i]+L))-tx[to].begin();
d[i]+=r-l;
}
}
if ((ll)x[i]+L<INF){
int to=lower_bound(ax+1,ax+n+1,x[i]+L)-ax;
if (ax[to]==x[i]+L){
l=lower_bound(tx[to].begin(),tx[to].end(),max(-INF,y[i]-L))-tx[to].begin();
r=upper_bound(tx[to].begin(),tx[to].end(),min(INF,y[i]+L))-tx[to].begin();
d[i]+=r-l;
}
}
if ((ll)y[i]-L>-INF){
int to=lower_bound(ay+1,ay+n+1,y[i]-L)-ay;
if (ay[to]==y[i]-L){
l=lower_bound(ty[to].begin(),ty[to].end(),max(-INF,x[i]-L+1))-ty[to].begin();
r=upper_bound(ty[to].begin(),ty[to].end(),min(INF,x[i]+L-1))-ty[to].begin();
d[i]+=r-l;
}
}
if ((ll)y[i]+L<INF){
int to=lower_bound(ay+1,ay+n+1,y[i]+L)-ay;
if (ay[to]==y[i]+L){
l=lower_bound(ty[to].begin(),ty[to].end(),max(-INF,x[i]-L+1))-ty[to].begin();
r=upper_bound(ty[to].begin(),ty[to].end(),min(INF,x[i]+L-1))-ty[to].begin();
d[i]+=r-l;
}
}
}
q.push(u);q.push(v);
while(!q.empty()){
int u=q.front();q.pop();
if (vis[u])continue;
vis[u]=1;
itor itl,itr;
if ((ll)x[u]-L>-INF){
int to=lower_bound(ax+1,ax+n+1,x[u]-L)-ax;
if (ax[to]==x[u]-L){
itl=sx[to].lower_bound(mp(max(-INF,y[u]-L),0));
itr=sx[to].upper_bound(mp(min(INF,y[u]+L),INF));
del(itl,itr,sx[to]);
}
}
if ((ll)x[u]+L<INF){
int to=lower_bound(ax+1,ax+n+1,x[u]+L)-ax;
if (ax[to]==x[u]+L){
itl=sx[to].lower_bound(mp(max(-INF,y[u]-L),0));
itr=sx[to].upper_bound(mp(min(INF,y[u]+L),INF));
del(itl,itr,sx[to]);
}
}
if ((ll)y[u]-L>-INF){
int to=lower_bound(ay+1,ay+n+1,y[u]-L)-ay;
if (ay[to]==y[u]-L){
itl=sy[to].lower_bound(mp(max(-INF,x[u]-L),0));
itr=sy[to].upper_bound(mp(min(INF,x[u]+L),INF));
del(itl,itr,sy[to]);
}
}
if ((ll)y[u]+L<INF){
int to=lower_bound(ay+1,ay+n+1,y[u]+L)-ay;
if (ay[to]==y[u]+L){
itl=sy[to].lower_bound(mp(max(-INF,x[u]-L),0));
itr=sy[to].upper_bound(mp(min(INF,x[u]+L),INF));
del(itl,itr,sy[to]);
}
}
}
ll ans=0;
for (int i=1;i<=n;i++)
if (vis[i])ans+=d[i];
printf("%lld",ans/2);
return 0;
}
```