#P17841. [ONTAK 2021]MIA

[ONTAK 2021]MIA

城市中的总部

无限网格中有 NN 个不同的单位格子作为居民区。两个居民区共用一条边时,它们之间有一条长度为 11 的双向道路。保证所有居民区连通。

请找出所有可以作为总部的居民区 (X0,Y0)(X_0,Y_0):对于每个居民区 (X,Y)(X,Y),必须存在一条完全经过居民区的道路路径,其长度恰好为曼哈顿距离 ∣X−X0∣+∣Y−Y0∣|X-X_0|+|Y-Y_0|。

输入格式

第一行 NN。接下来 NN 行,每行两个整数 xi,yix_i,y_i,表示居民区坐标。

输出格式

第一行输出符合条件的居民区数 KK。接下来 KK 行输出这些居民区的坐标,可以按任意顺序输出,不能重复。KK 可以为 00。

数据范围

1≤N≤4000001\le N\le400000,−106≤xi,yi≤106-10^6\le x_i,y_i\le10^6,坐标互不相同。

样例

13
0 0
0 1
0 2
0 3
1 0
1 3
2 0
2 2
2 3
3 0
3 1
3 2
3 3
3
0 3
3 0
3 3