idealcity.cpp

#include <bits/stdc++.h>

using namespace std;
using llint = long long;

const int MAXN = 100100;
const llint MOD = 1e9;

int n;
pair<int, int> points[MAXN];
int nxt_id;
int id[MAXN];
vector<int> edges[MAXN];
bool bio[MAXN];
map<pair<int, int>, int> cells;

llint w[MAXN];
llint stsize[MAXN];

llint dfs(int i);

llint spread(int i, int k)
{
	edges[id[i]].push_back(id[k]);
	llint ret = (dfs(k) + stsize[id[k]] * (n - stsize[id[k]])) % MOD;
	stsize[id[i]] += stsize[id[k]];
	return ret;
}

llint tryspread(int i, int j)
{
	llint ret = 0;
	
	try
	{
		int k = cells.at({points[j].first - 1, points[j].second});
		if (!bio[k])
		{
			ret += spread(i, k);
		}
	}
	catch (out_of_range) {}
	try
	{
		int k = cells.at({points[j].first + 1, points[j].second});
		if (!bio[k])
		{
			ret += spread(i, k);
		}
	}
	catch (out_of_range) {}
	
	return ret % MOD;
}

llint dfs(int i)
{
	bio[i] = true;
	id[i] = nxt_id++;
	stsize[id[i]] = 0;
	
	llint ret = 0;
	
	for (int j = i - 1; j >= 0 && points[j].first == points[i].first && points[j].second - points[i].second == j - i; --j)
	{
		++stsize[id[i]];
		bio[j] = true;
		id[j] = id[i];
	}
	for (int j = i; j < n && points[j].first == points[i].first && points[j].second - points[i].second == j - i; ++j)
	{
		++stsize[id[i]];
		bio[j] = true;
		id[j] = id[i];
	}
	
	for (int j = i - 1; j >= 0 && points[j].first == points[i].first && points[j].second - points[i].second == j - i; --j)
	{
		ret += tryspread(i, j);
	}
	for (int j = i; j < n && points[j].first == points[i].first && points[j].second - points[i].second == j - i; ++j)
	{
		ret += tryspread(i, j);
	}
	
	return ret % MOD;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int i;
	llint sol = 0;
	
	cin>>n;
	
	for (i = 0; i < n; ++i)
		cin>>points[i].first>>points[i].second;
	
	for (int k = 0; k < 2; ++k)
	{
		sort(points, points + n);
		
		cells.clear();
		for (i = 0; i < n; ++i)
			cells[points[i]] = i;
		
		fill(bio, bio + n, false);
		nxt_id = 0;
		
		sol += dfs(0);
		
		for (i = 0; i < n; ++i)
			swap(points[i].first, points[i].second);
	}
	
	cout<<sol % MOD<<'\n';
}