继续2—SAT+二分，，n个正方形，每个点在正方形上边或下边的终点，每个点就有两种选择，2—SAT建图，，
此题有两种建图的方式:
一：分四种情况；i向上，j向上，判断两正方形是否相交，如果相交建边i—>j'，j—>i'；
i向上，j向下，判断两正方形是否相交，如果相交建边i—>j，j’—>i'；
i向下，j向上，判断两正方形是否相交，如果相交建边i'—>j'，j—>i；
i向下，j向下，判断两正方形是否相交，如果相交建边i'—>j，j'—>i；
二：直接判断两个正方形怎么放不相交，但这样的话容易漏掉应该加的边，这题的i必须向上，j必须向下的情况，
就要加上边(i+n,i)，(j，j+n)，表示i必须向上，j必须向下，如果不加就wrong。这种建边方式不太习惯，
#include<stdio.h>
#include<string.h>
#include<stack>
#define N 300
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
using namespace std;
struct edge
{
int ed,next;
}E[N*N];
struct op
{
int x,y;
}p[N];
int low[N],dfs[N],belong[N],ins[N],idx,ans,num,first[N],n;
void addedge(int x,int y)
{
E[num].ed=y;
E[num].next=first[x];
first[x]=num++;
}
int cmp(const void *a,const void *b)
{
struct op *c,*d;
c=(struct op *)a;
d=(struct op *)b;
return d->y-c->y;
}
void insit()
{
memset(low,0,sizeof(low));
memset(dfs,-1,sizeof(dfs));
memset(belong,0,sizeof(belong));
memset(ins,0,sizeof(ins));
memset(first,-1,sizeof(first));
idx=ans=num=0;
}
stack<int>Q;
void Tarjan(int x)
{
int v,p;
low[x]=dfs[x]=idx++;
Q.push(x);
ins[x]=1;
for(p=first[x];p!=-1;p=E[p].next)
{
v=E[p].ed;
if(dfs[v]==-1)
{
Tarjan(v);
low[x]=low[x]>low[v]?low[v]:low[x];
}
else if(ins[v]==1)
low[x]=low[x]>dfs[v]?dfs[v]:low[x];
}
if(dfs[x]==low[x])
{
do
{
v=Q.top();
Q.pop();
ins[v]=0;
belong[v]=ans;
}while(v!=x);
ans++;
}
}
bool cross(int mid,int i,int j,int s1,int s2)
{
double x1=p[i].x-mid/2.0,x2=p[i].x+mid/2.0;
double y1=p[i].y,y2=p[i].y+s1*mid;
double x3=p[j].x-mid/2.0,x4=p[j].x+mid/2.0;
double y3=p[j].y,y4=p[j].y+s2*mid;
if(max(x1,x2)<=min(x3,x4))return false;
if(min(x1,x2)>=max(x3,x4))return false;
if(max(y1,y2)<=min(y3,y4))return false;
if(min(y1,y2)>=max(y3,y4))return false;
return true;
}
int judge(int d)
{
int i,j;
insit();
for(i=0;i<n;i++)
for(j=i+1;j<n;j++)
{
//*********************************************************************************
/*
if(abs(p[i].x-p[j].x)>=d)continue;//横坐标的距离大于d，怎么放都不会重合
if(p[i].y-p[j].y>=2*d)continue;//纵坐标大于2d，
if(p[i].y-p[j].y<d)//距离小于d，只能一上一下
{
if(p[i].y==p[j].y)
{
addedge(i,j+n);//i上，j下
addedge(j,i+n);//j上，i下
addedge(i+n,j);
addedge(j+n,i);
}
else
{
addedge(i,j+n);//i向上，j向下(i与j矛盾）
addedge(i+n,i);//i一定向上
addedge(j,j+n);//j一定向下
addedge(j+n,i);//(j'与i'矛盾）
}
}
else if(p[i].y-p[j].y<2*d)
{
addedge(i+n,j+n);//都向下
addedge(j,i);//都向上
}
*/
//*********************************************************************************
if(cross(d,i,j,1,1))//1代表向上，-1代表向下
{
addedge(i,j+n);
addedge(j,i+n);
}
if(cross(d,i,j,1,-1))
{
addedge(i,j);
addedge(j+n,i+n);
}
if(cross(d,i,j,-1,1))
{
addedge(i+n,j+n);
addedge(j,i);
}
if(cross(d,i,j,-1,-1))
{
addedge(i+n,j);
addedge(j+n,i);
}
}
for(i=0;i<n*2;i++)
if(dfs[i]==-1)
Tarjan(i);
for(i=0;i<n;i++)
if(belong[i]==belong[i+n])
return 0;
return 1;
}
int main()
{
int i,t,min,max,mid,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d",&p[i].x,&p[i].y);
qsort(p,n,sizeof(p[0]),cmp);
min=0;max=20000;
sum=0;
while(min<=max)
{
mid=(min+max)/2;
if(judge(mid))
{
sum=mid;
min=mid+1;
}
else max=mid-1;
}
printf("%d\n",sum);
}
return 0;
}