「CEOI2019」建造摩天楼

显然是倒着考虑删除每个大楼，此时每次面临的情况都是一个子问题

下文称当前局面未被删除的大楼为黑点，其余为白点

子问题有解的充要条件是：黑点之间能 8-连通

当前一个点能够被删掉的条件是：

1.这个点能够连通到无穷处

2.这个点不是当前8-连通图的割点

考虑用一个简单的方法维护条件1：

将一开始每个黑点周围的白点取出，按照白点之间4-连通构建连通块

能够4-连通接触到最外层连通块的黑点满足条件1

每次删除黑点之后，增加能够连通的白点，每个白点只会增加一次

ps:寻找最外层4-连通白点的一个方法：找到x最大的白点

接下来考虑如何判定一个点$u$是否是割点：

首先删除$u$之后，周围8连通内能够构成多个连通块，可以发现大致可以归结为以下几种情况，其中x,y为黑点

多个$x$表示$x$在其中任何一个位置都可以

1.
x ① y
x u y
x ② y
2.
x ① y
② u y
y y y

对于这两种情况，只要白点1和白点2在同一4-连通块，割掉$u$就会分开x和$y$

由此，每次插入一个白点，可以$O(1)$检测一个点是否合法

简单讨论可以发现，会被影响合法性的点，一定在新加入最外层连通块的白点周围

这样总共check了$O(n)$次，每次用一个堆/set维护能选的最大编号的点即可

ps:代码非常丑非常垃圾。。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<bits/stdc++.h>
using namespace std;

typedef pair <int,int> Pii;
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=1.3e6+10,INF=1e9+10;
const int z[5][4]={ {1,0},{0,-1},{-1,0},{0,1} };
const int Z[9][4]={ {1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1},{0,1} };

int n,m,k;
int F[N];
int Find(int x){ return F[x]==x?x:F[x]=Find(F[x]);}
void Union(int x,int y){ F[Find(x)]=Find(y); }
map <Pii,int> B,W;
set <int> st;
vector <int> ans;
Pii A[N],P[N];
int ma=-1e9,maxid;
int G[N][4];
void Ins(int x,int y){
    // Insert white point
	Pii T=mp(x,y);
	if(B.count(T)) return ;
	if(!W.count(T)) P[W[T]=++m]=T,F[m]=m;
	int u=W[T];
	if(x>ma) ma=x,maxid=u;
	rep(i,0,3) {
		int x1=x+z[i][0],y1=y+z[i][1];
		if(W.count(mp(x1,y1))) {
			int v=W[mp(x1,y1)];
			G[u][i]=v;
			G[v][(i+2)%4]=u;
			Union(u,v);
		}
	}
}

int del[N],vis[N],reach[N];
int Check(int u){
	if(del[u]||!reach[u]) return 0;
	static int I[8];
	int c=0;
	rep(i,0,7) {
		Pii T=mp(A[u].x+Z[i][0],A[u].y+Z[i][1]);
		if(W.count(T)) I[i]=Find(W[T]);
		else I[i]=0,c++;
	}
	for(int i=1,t=0;t<4;t++,i=(i+2)%8){
		int j=(i+2)%8;
		if(I[i] && I[i]==I[j] && !I[(i+1)%8] && c>1) return 0;
	}
	if((!I[0]||!I[1]||!I[2]) && (!I[4]||!I[5]||!I[6]) && I[3] && I[3]==I[7]) return 0;
	if((!I[2]||!I[3]||!I[4]) && (!I[6]||!I[7]||!I[0]) && I[1] && I[5]==I[1]) return 0;
	return 1;
}
void ReCheck(int u){
	auto it=st.find(u);
	if(it!=st.end()) st.erase(it);
	if(Check(u)) st.insert(u);
}

vector <int> tmp;
void dfs(int u){
	if(!u) return;
	if(vis[u]) return;
	vis[u]=1;
	rep(i,0,3) {
		if(G[u][i]) dfs(G[u][i]);
		Pii T=mp(P[u].x+z[i][0],P[u].y+z[i][1]);
		if(B.count(T)) reach[B[T]]=1;
	}
	rep(dx,-1,1) rep(dy,-1,1) if(dx||dy) {
		Pii T=mp(P[u].x+dx,P[u].y+dy);
		if(B.count(T)) tmp.pb(B[T]);
	}
}
void Dfs(int u){
	dfs(u);
	sort(tmp.begin(),tmp.end()),tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
	for(int i:tmp) ReCheck(i);
	tmp.clear();
}

void Del(int u){
    // delete black point
	del[u]=1;
	B.erase(A[u]),Ins(A[u].x,A[u].y);
	Dfs(W[A[u]]);
}

int main(){
	n=rd(),rd();
	rep(i,1,n) A[i].x=rd(),A[i].y=rd(),B[A[i]]=i;
	rep(i,1,n) F[i]=i;
	
	// Check NO
	rep(i,1,n) { 
		rep(dx,-1,1) rep(dy,-1,1) {
			Pii T=mp(A[i].x+dx,A[i].y+dy);
			if(B.count(T)) Union(i,B[T]);
		}
	}
	rep(i,1,n) if(Find(i)!=Find(1)) return puts("NO"),0;

	rep(i,1,n) rep(dx,-1,1) rep(dy,-1,1) if(dx||dy) Ins(A[i].x+dx,A[i].y+dy);
	Dfs(maxid);

	rep(i,1,n) {
		int u=*st.rbegin();
		auto it=st.end(); --it;st.erase(it);
		Del(u),ans.pb(u);
	}
	reverse(ans.begin(),ans.end());
	puts("YES");
	for(int i:ans) printf("%d\n",i);
}