题意分析

我们需要在地图上为多个城市点标注正方形标签，要求：

1. 每个标签尺寸相同（边长为整数$s$）
2. 城市点必须位于标签上边或下边的中点
3. 标签之间不能重叠（允许边重合）
4. 求能满足条件的最大标签尺寸$s_{max}$

关键约束：

• 城市坐标$(X_i,Y_i)$为整数（$-10000 \leq X,Y \leq 10000$）
• 城市数量$3 \leq m \leq 100$
• 标签位置有2种选择（城市点在标签上边或下边）

解题思路

1. 问题转化：

   • 每个标签可视为两个候选矩形（上方放置/下方放置）
   • 对于给定尺寸$s$，检查是否存在一种标签位置选择，使得所有矩形不重叠
   • 通过二分搜索寻找最大可行的$s$

2. 冲突检测：

   • 对于两个城市点$(X_i,Y_i)$和$(X_j,Y_j)$
   • 若选择相同方向（均在上或均在下）：
     • 垂直间距需$\geq s$
     • 水平间距需$\geq s$
   • 若选择不同方向：
     • 垂直间距需$\geq 0$
     • 水平间距需$\geq s$

3. 二分搜索：

   • 搜索范围：$s \in [1, 20000]$（因坐标范围$\pm 10000$）
   • 验证函数：用DFS/BFS检查是否存在合法的标签位置组合

实现步骤

1. 输入处理：

   • 读取城市坐标，存储为$(X_i,Y_i)$数组

2. 二分搜索框架

3. 冲突检查函数：

   • 构建冲突图：若两个标签在某个放置方式下会重叠，则记录冲突
   • 使用2-SAT或DFS检查是否存在无冲突的选择方案

4. 输出结果：

   • 二分搜索结束后输出$right$值

代码实现

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
 
#define REP( i , a , b ) for ( int i = ( a ) ; i < ( b ) ; ++ i )
#define FOR( i , a , b ) for ( int i = ( a ) ; i <= ( b ) ; ++ i )
#define REV( i , a , b ) for ( int i = ( a ) ; i >= ( b ) ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
 
const int MAXN = 205 ;
const int MAXE = 40000 ;
 
struct Edge {
	int v ;
	Edge* next ;
} ;
 
struct Line {
	int x , y ;
} ;
 
Edge E[MAXE] , *H[MAXN] , *cur ;
int dfn[MAXN] , low[MAXN] , scc[MAXN] , scc_cnt ;
int S[MAXN] , top , dfs_clock ;
int n ;
 
Line l[MAXN] ;
 
void init () {
	cur = E ;
	top = 0 ;
	scc_cnt = 0 ;
	dfs_clock = 0 ;
	CLR ( H , 0 ) ;
	CLR ( dfn , 0 ) ;
	CLR ( scc , 0 ) ;
}
 
void addedge ( int u , int v ) {
	cur -> v = v ;
	cur -> next = H[u] ;
	H[u] = cur ++ ;
}
 
void tarjan ( int u ) {
	dfn[u] = low[u] = ++ dfs_clock ;
	S[top ++] = u ;
	for ( Edge* e = H[u] ; e ; e = e -> next ) {
		int v = e -> v ;
		if ( !dfn[v] ) {
			tarjan ( v ) ;
			low[u] = min ( low[u] , low[v] ) ;
		} else if ( !scc[v] ) low[u] = min ( low[u] , dfn[v] ) ;
	}
	if ( low[u] == dfn[u] ) {
		++ scc_cnt ;
		do {
			scc[S[-- top]] = scc_cnt ;
		} while ( u != S[top] ) ;
	}
}
 
/*
void scanf ( int& x , char c = 0 ) {
	while ( ( c = getchar () ) < '0' || c > '9' ) ;
	x = c - '0' ;
	while ( ( c = getchar () ) >= '0' && c <= '9' ) x = x * 10 + c - '0' ;
}
*/
 
bool ok () {
	REP ( i , 0 , n << 1 ) if ( !dfn[i] ) tarjan ( i ) ;
	REP ( i , 0 , n ) if ( scc[i << 1] == scc[i << 1 | 1] ) return 0 ;
	return 1 ;
}
 
void solve () {
	scanf ( "%d" , &n ) ;
	REP ( i , 0 , n ) scanf ( "%d%d" , &l[i].x , &l[i].y ) ;
	int low = 0 , high = 20000 ;
	while ( low < high ) {
		int m = ( low + high ) >> 1 ;
		init () ;
		REP ( i , 0 , n ) REP ( j , i + 1 , n ) {
			if ( abs ( l[i].x - l[j].x ) >= m ) continue ;
			if ( abs ( l[i].y - l[j].y ) >= 2 * m ) continue ;
			if ( abs ( l[i].y - l[j].y ) >= m ) {
				if ( l[i].y < l[j].y ) {
					addedge ( i << 1 , j << 1 ) ;
					addedge ( j << 1 | 1 , i << 1 | 1 ) ;
				} else {
					addedge ( i << 1 | 1 , j << 1 | 1 ) ;
					addedge ( j << 1 , i << 1 ) ;
				}
			} else {
				if ( l[i].y < l[j].y ) {
					addedge ( i << 1 , i << 1 | 1 ) ;
					addedge ( j << 1 | 1 , j << 1 ) ;
				} else if ( l[i].y > l[j].y ) {
					addedge ( i << 1 | 1 , i << 1 ) ;
					addedge ( j << 1 , j << 1 | 1 ) ;
				} else {
					addedge ( i << 1 , j << 1 | 1 ) ;
					addedge ( j << 1 , i << 1 | 1 ) ;
					addedge ( i << 1 | 1 , j << 1 ) ;
					addedge ( j << 1 | 1 , i << 1 ) ;
				}
			}
		}
		if ( ok () ) low = m + 1 ;
		else high = m ;
	}
	printf ( "%d\n" , low - 1 ) ;
}
 
int main () {
	int T ;
	scanf ( "%d" , &T ) ;
	while ( T -- ) solve () ;
	return 0 ;
}