Submission #1869545

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#include<set>
#include<map>
#define sqr(x) (x)*(x)
using namespace std;
long long n,m,a,b,i,j,dax[100005],day[100005],used[100005],ans,x,y,dis;
map<int,set<pair<int,int>/**/>/**/> row,col;
vector<int> lsx,lsy;
void dfs(int x)
{
	if (used[x]) return;
	used[x]=1;
	int i;
	vector<pair<int,int>/**/> era;
	set<pair<int,int>/**/>::iterator lb=row[dax[x]-dis].lower_bound(make_pair(day[x]-dis,0));
	set<pair<int,int>/**/>::iterator ub=row[dax[x]-dis].upper_bound(make_pair(day[x]+dis,1e18));
	for (set<pair<int,int>/**/>::iterator it=lb;it!=ub;it++)
	//col[(*it).first].erase(make_pair(dax[x]-dis,(*it).second)),row.erase(it++))
	{
		ans++;
		dfs((*it).second);
	}
	lb=row[dax[x]+dis].lower_bound(make_pair(day[x]-dis,0));
	ub=row[dax[x]+dis].upper_bound(make_pair(day[x]+dis,1e18));
	for (set<pair<int,int>/**/>::iterator it=lb;it!=ub;it++)
	//col[(*it).first].erase(make_pair(dax[x]-dis,(*it).second)),row.erase(it++))
	{
		ans++;
		dfs((*it).second);
	}
	lb=col[day[x]-dis].lower_bound(make_pair(day[x]-dis,0));
	ub=col[day[x]-dis].upper_bound(make_pair(day[x]+dis,1e18));
	for (set<pair<int,int>/**/>::iterator it=lb;it!=ub;it++)
	//row[(*it).first].erase(make_pair(day[x]-dis,(*it).second)),col.erase(it++))
	{
		ans++;
		dfs((*it).second);
	}
	lb=col[day[x]+dis].lower_bound(make_pair(day[x]-dis,0));
	ub=col[day[x]+dis].upper_bound(make_pair(day[x]+dis,1e18));
	for (set<pair<int,int>/**/>::iterator it=lb;it!=ub;it++)
	//row[(*it).first].erase(make_pair(day[x]-dis,(*it).second)),col.erase(it++))
	{
		ans++;
		dfs((*it).second);
	}
}
int main()
{
	cin>>n>>a>>b;
	for (i=1;i<=n;i++)
	{
		cin>>x>>y;
		dax[i]=x+y;
		day[i]=x-y;
		row[x+y].insert(make_pair(x-y,i));
		col[x-y].insert(make_pair(x+y,i));
		//lsx.push_back(dax[i]);
		//lsy.push_back(day[i]);
	}
	/*sort(lsx.begin(),lsx.end());
	unique(lsx.begin(),lsx.end());
	sort(lsy.begin(),lsy.end());
	unique(lsy.begin(),lsy.end());
	for (i=1;i<=n;i++)
	{
		dax[i]=upper_bound(lsx.begin(),lsx.end(),dax[i])-lsx.begin()+2;
		day[i]=upper_bound(lsy.begin(),lsy.end(),day[i])-lsy.begin()+2;
	}*/
	dis=max(abs(dax[a]-dax[b]),abs(day[a]-day[b]));
	dfs(a);
	dfs(b);
	cout<<ans;
	return 0;
}

Submission Info

Judge Result