Codeforces #951 : Div2 E. Manhattan Triangle

こちらは割とすんなり。
https://codeforces.com/contest/1979/problem/E

問題

2次元座標上でN個の点が与えられる。
また、整数Dが指定される。

N点中3点のうち、どの2点もマンハッタン距離がDとなる組があれば1つ答えよ。

解法

3点中2点は、ちょうど45度の位置に配置される。
もし2点が(x,y)と(x+D/2,y+D/2)にある場合、3点目があり得るなら(x-D/2,y)と(x,y+D/2)を結ぶ線分上か、(x+D/2,y-D/2)と(x+D,y)を結ぶ線分上のいずれかである。

これをシミュレートしよう。
頂点(x,y)がy=x+kの直線に乗る場合、そのような直線を同じグループに載せよう。

(x,y)を総当たりし、(x+D/2,y+D/2)に他の点があるか調べる。
y=x+kであるなら、y=x+k+Dやy=x+k-D上に乗る頂点が存在するかチェックし、x座標・y座標が範囲内かチェックすればよい。

int T,N,D;
int X[202020],Y[202020];

vector<pair<int,int>> XpY[404040];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>D;
		FOR(i,N) {
			cin>>X[i]>>Y[i];
		}
		vector<int> ret={0,0,0};
		FOR(j,2) {
			set<int> Sp;
			FOR(i,N) {
				XpY[X[i]+Y[i]+202020].push_back({X[i],i});
				Sp.insert(X[i]+Y[i]+202020);
			}
			FORR(a,Sp) sort(ALL(XpY[a]));
			FORR(a,Sp) {
				for(int L=0,R=0;L<XpY[a].size();L++) {
					while(R<XpY[a].size()&&XpY[a][R].first-XpY[a][L].first<D/2) R++;
					if(R==XpY[a].size()) break;
					if(XpY[a][R].first-XpY[a][L].first==D/2) {
						if(a+D<=402020&&XpY[a+D].size()) {
							x=lower_bound(ALL(XpY[a+D]),make_pair(XpY[a][R].first,0))-XpY[a+D].begin();
							if(x<XpY[a+D].size()&&Y[XpY[a+D][x].second]>=Y[XpY[a][L].second]) {
								ret={XpY[a][L].second+1,XpY[a][R].second+1,XpY[a+D][x].second+1};
							}
						}
						if(a-D>=0&&XpY[a-D].size()) {
							x=lower_bound(ALL(XpY[a-D]),make_pair(XpY[a][L].first+1,0))-XpY[a-D].begin();
							
							if(x>0&&Y[XpY[a-D][x-1].second]<=Y[XpY[a][R].second]) {
								ret={XpY[a][L].second+1,XpY[a][R].second+1,XpY[a-D][x-1].second+1};
							}
						}
						
					}
				}
			}
			FORR(a,Sp) XpY[a].clear();
			FOR(i,N) Y[i]=-Y[i];
		}
		cout<<ret[0]<<" "<<ret[1]<<" "<<ret[2]<<endl;
	}
		
		
		
}

まとめ

典型っぽい。