poj 2296 (2 - SAT + 2 점)

계속 2 - SAT + 2 점, n 개의 정사각형, 각 점 은 정사각형 상단 이나 아래쪽 의 종점 에 있 고 각 점 마다 두 가지 선택 이 있 습 니 다. 2 - SAT 건축 도,
이 문 제 는 두 가지 그림 을 만 드 는 방식 이 있다.
1. 네 가지 상황 으로 나 뉜 다.i 위로, j 위로, 두 정사각형 이 교차 하 는 지 여 부 를 판단 하고 교차 하면 건축 변 i - > j ', j - > i';
                           i 위로, j 아래로, 두 정사각형 이 교차 하 는 지 여 부 를 판단 합 니 다. 만약 에 교차 하면 건축 변 i - > j, j - > i ';
                           i 아래로, j 위로, 두 정사각형 이 교차 하 는 지 여 부 를 판단 합 니 다. 만약 에 교차 하면 건축 변 i '- > j', j - > i;
                           i 아래로, j 아래로, 두 정사각형 이 교차 하 는 지 여 부 를 판단 하고, 교차 하면 변경 i '- > j, j' - > i;
2. 두 정사각형 이 어떻게 서로 교차 하지 않 는 지 직접 판단 하지만 이렇게 하면 넣 어야 할 변 을 빠 뜨리 기 쉽다. 이 문제 의 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
",sum);
	}
	return 0;
}