根据题意，我们可以把位于同一行且左右相邻的点连成一条横边，把位于同一列且上下相邻的点连成一条竖边（这里的“相邻”指的是两个点在横向或竖向上之间没有输入给出的黑点，一个点可以参与多条边）。

比如，我们可以把一个图连成这样：

那么，不难发现，能够变成黑点的白点都是位于线段交点上的点。

那么，如何去统计线段交点呢？

我们可以把可以把边分成两类：横向边（和x轴平行的边）和纵向边（和y轴平行的边）。于是，统计交点就等同于每条横向边于纵向 边交点个数的和。而对于这个和，我们可以用扫描线的方法求得。

大体思路是这样的：

如果扫描线是从上到下进行扫描的，则我们可以用线段树树状数组来记录有多少条纵向边经过了$y=k$。

为了方便理解，我们可以先用一个最普通的数组$t_{1,9}$来记录纵边经过点$y=k$的距离。如下图，若我们以$y=4$为例，则$t_{1,9}=0,1,0,0,0,0,1,0,0$，其中两个$1$表示的便是两个交点。而对于查询，交点数量便是线段GI、线段IH上交点数量的和。我们发现，如果直接在刚刚的数组$t_{1,9}$中统计，那么复杂度为$O(n)$。我们可以用树状数组来优化这一步，来完成这个本质上是区间求和的工作。

对于树状数组的修改，我们只需在纵边的第一个点被扫到时在数组的对应位置加一，在纵边的第二个点被扫到后在对应位置减一即可。

code:

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
#define ll long long
#define INF 0x7fffffff
#define qwq printf("qwq\n");

using namespace std;

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

struct node {
	int x, y;
}u[400005];

struct edge {
	int up, down, left, right;
}e[400005];

struct edge_end {
	int x, y;
	bool operator < (const edge_end &a) const {return a.y < y;}
};

int n, m, cnt, ans, maxx, a[400005], t[400005];

priority_queue<edge_end> que;

void Read_in() {
	n = read();
	for(int i = 1; i <= n; i++) {
		u[i].x = read(); u[i].y = read();
		a[++cnt] = u[i].x; a[++cnt] = u[i].y;
	}
}

void Discretization() {
	sort(a + 1, a + cnt + 1);
	cnt = unique(a + 1, a + cnt + 1) - a - 1;
	for(int i = 1; i <= n; i++) {
		u[i].x = lower_bound(a + 1, a + cnt + 1, u[i].x) - a;
		u[i].y = lower_bound(a + 1, a + cnt + 1, u[i].y) - a;
		maxx = max(maxx, u[i].x);
	}
}

bool xsort(node a, node b) {return a.x == b.x ? a.y < b.y : a.x < b.x;}
bool ysort(node a, node b) {return a.y == b.y ? a.x < b.x : a.y < b.y;}
bool esort(edge a, edge b) {return a.up == b.up ? a.left < b.left : a.up < b.up;}

void Make_edge() {
	sort(u + 1, u + n + 1, xsort);    // x 相同    处理竖边 
	for(int i = 1; i < n; i++) {
		if(u[i + 1].x != u[i].x || u[i + 1].y - u[i].y < 2) continue;
		e[++m].up = u[i].y + 1; e[m].down = u[i + 1].y - 1; e[m].right = u[i].x;
	}
	sort(u + 1, u + n + 1, ysort);    // y 相同    处理横边 
	for(int i = 1; i < n; i++) {
		if(u[i + 1].y != u[i].y || u[i + 1].x - u[i].x < 2) continue;
		e[++m].up = u[i].y; e[m].left = u[i].x + 1; e[m].right = u[i + 1].x - 1;
	}
	sort(e + 1, e + m + 1, esort);
}

int lowbit(int x) {return x & -x;}
void update(int x, int k) {while(x <= maxx) {t[x] = t[x] + k; x = x + lowbit(x);}}
int query(int x) {int ans = 0; while(x) {ans = ans + t[x]; x = x - lowbit(x);} return ans;}

void Scanning() {
	for(int i = 1; i <= m; i++) {
		int deep = e[i].up;
		while(!que.empty() && que.top().y <= deep) {update(que.top().x, -1); que.pop();}
		if(!e[i].left) {update(e[i].right, 1); que.push((edge_end){e[i].right, e[i].down + 1});}
		else {ans = ans + query(e[i].right) - query(e[i].left - 1);}
	}
}

void Print() {printf("%d\n", ans + n);}

int main() {
	Read_in();
	Discretization();
	Make_edge();
	Scanning();
	Print();
    return 0;
}

扫描线板子题。

传送门

对于新手来说能比较好的进一步理解。

首先我们需要离散化。

接着观察性质。

不难发现，除了初始的黑点以外，新生成的黑点是不会对其他白点产生影响的。

同时，是不会出现一直变化的情况的。

对于一对 $x$ 坐标相等且之间没有其他黑点的点，他们的贡献是 $x$ 这个位置，在 $y_i+1\sim y_j-1$ 之间，只要有另一对 $y$ 坐标相等的点出现吗，那么就会新产生一个黑点。

这很类似与扫描线，将矩形的某一条边转化为操作。

那么我们考虑扫描的过程。

我们可以将所有的 $x$ 坐标相等的点对看成单点修改，一段时间后擦除。

对于 $y$ 坐标相同的点对，我们可以看做在 $y$ 这个时刻区间询问 $x_i\sim x_j$ 之间有多少个被标记的点。

我们使用一个优先队列，存储每一个 $x$ 坐标相等的点对。

将 $y$ 坐标比较小的作为单点加，大的作为单点减。

再用一个优先队列，存储每一个 $y$ 坐标相等的点对。

按照 $y$ 坐标顺序，一个一个的加入（删除）单点。

对于每一个区间（ $y$ 坐标相等的点对）查询里面有多少个点。

将所有答案求出，最后在加上 $n$ 即为答案。

注意，点对必须之间什么都没有！

否则你可能得到 $20$ 或者 $40$ pts。

细节看看代码。

$\text {CODE}$

#include<bits/stdc++.h>
#define N 1000006
#define ls (now<<1)
#define rs (now<<1|1)
using namespace std;
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;
}
int n,x[N],y[N],ans;
struct node
{
	int x,y;
}e[N];
bool cmp(node a,node b)
{
	if(a.x==b.x)return a.y<b.y;
	return a.x<b.x;
}
bool bnq(node a,node b)
{
	if(a.y==b.y)return a.x<b.x;
	return a.y<b.y;
}
struct pos
{
	int x,t,val;
	bool operator <(pos b)const
	{return t>b.t;}
};
priority_queue<pos> q;
int tr[N];
void up(int now){tr[now]=tr[ls]+tr[rs];}
void midy(int now,int l,int r,int x,int val)
{
	if(l==r)
	{
		tr[now]+=val;
		return ;
	}
	int mid=(l+r)>>1;
	if(mid>=x)midy(ls,l,mid,x,val);
	else midy(rs,mid+1,r,x,val);
	up(now);
}
void que(int now,int l,int r,int ql,int qr)
{
	if(ql>qr)return ;
	if(l>=ql&&r<=qr)
	{
		ans+=tr[now];
		return;
	}
	int mid=(l+r)>>1;
	if(mid>=ql)que(ls,l,mid,ql,qr);
	if(mid<qr)que(rs,mid+1,r,ql,qr);
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
	{
		e[i].x=read();
		e[i].y=read();
		x[i]=e[i].x;
		y[i]=e[i].y;
	}
	sort(x+1,x+1+n);int lenx=unique(x+1,x+1+n)-x-1;
	sort(y+1,y+1+n);int leny=unique(y+1,y+1+n)-y-1;
	for(int i=1;i<=n;i++)
	{
		e[i].x=lower_bound(x+1,x+1+lenx,e[i].x)-x;
		e[i].y=lower_bound(y+1,y+1+leny,e[i].y)-y;
	}
	sort(e+1,e+1+n,cmp);
	for(int i=1,l;i<n;)
	{
		l=i;
		while(e[i].x==e[l].x&&l<n)
		{
			l++;
			if(e[i].x!=e[l].x)continue;
			if(e[l-1].y<e[l].y-1)
			{
				q.push(pos{e[l-1].x,e[l-1].y+1,1});
				q.push(pos{e[l].x,e[l].y,-1});
			}
		}
		i=l;
	}
	sort(e+1,e+1+n,bnq);
	for(int i=1,l;i<n;)
	{
		l=i;
		while(q.size()&&q.top().t<=e[i].y)
		{
			midy(1,1,lenx,q.top().x,q.top().val);
			q.pop();
		}
		while(e[i].y==e[l].y&&l<n)
		{
			l++;
			if(e[i].y!=e[l].y)continue;
			que(1,1,lenx,e[l-1].x+1,e[l].x-1);
		}
		i=l;
	}
	cout<<ans+n<<"\n";
	return 0;
}