Submission #9798110

---

Source Code Expand

#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
const int N=100000;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u];i;i=sq[i].nxt)
#define fir first
#define sec second
#define mp(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define maxd 998244353
#define eps 1e-8
struct node{int to,nxt;}sq[1000200];
int all=0,head[100100];
int n,m,d[100100],dis,a,b;
ll ans=0;
bool vis[100100];
struct pnode{int x,y,id;}p[100100];
bool operator <(pnode p,pnode q) 
{
	return ((p.x<q.x) || ((p.x==q.x) && (p.y<q.y)));
}

int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

void add(int u,int v)
{
	all++;sq[all].to=v;sq[all].nxt=head[u];head[u]=all;
}

void solve(int nowd)
{
	sort(p+1,p+1+n);
	int l=1,r=0,pos=1;
	rep(i,1,n)
	{
		while ((l<n) && ((p[i].x-dis>p[l].x) || ((p[i].x-dis==p[l].x) && (p[i].y-nowd>p[l].y)))) l++;
		while ((r<n) && ((p[i].x-dis>p[r+1].x) || ((p[i].x-dis==p[r+1].x) && (p[i].y+nowd>=p[r+1].y)))) r++;
		d[p[i].id]+=r-l+1;pos=max(pos,l);
		while (pos<=r) 
		{
			add(p[i].id,p[pos].id);add(p[pos].id,p[i].id);
			pos++;
		}
		pos--;
	}
}

void dfs(int u)
{
	ans+=d[u];vis[u]=1;
	go(u,i)
	{
		int v=sq[i].to;
		if (!vis[v]) dfs(v);
	}
}

int main()
{
	n=read();a=read();b=read();
	rep(i,1,n) 
	{
		int x=read(),y=read();
		p[i]=(pnode){x+y,x-y,i};
	}
	dis=max(abs(p[a].x-p[b].x),abs(p[a].y-p[b].y));
	solve(dis);
	rep(i,1,n) swap(p[i].x,p[i].y);
	solve(dis-1);
	dfs(a);
	printf("%lld",ans);
	return 0;
}

Submission Info

Judge Result