题目
题目链接：http://poj.org/problem?id=2296
一个平面直角坐标系里有 \(n\) 个点，要求使这些点每一个都在一个具有一定长度的正方形的上边或下边（正方形不能重合，边界可以重叠），求这个正方形的最大边长。
注意：这道题每个点先输入的是纵坐标，其次才是横坐标。
思路
首先显然正方形边长满足单调性，所以二分最大边长 \(mid\)。
考虑如何判定一个答案是否合法，如果两个点 \(a,b\) 满足 \(|a_y-b_y|<mid\)，那么这两个点放正方形就会有影响。
由于每个点放正方形的方案就只有两种，所以考虑变成 2-sat 问题。设 \(a\) 表示点 \(a\) 的正方形往上放，\(a+n\) 表示 \(a\) 的正方形往下放。
设 \(a_x\geq b_x\)：
- 如果 \(a_x=b_x\)，那么两个正方形一定是一上一下，那么连边 \((a,b+n),(a+n,b),(b,a+n),(b+n,a)\)。
- 如果 \(0<a_x-b_x<mid\)，那么 \(a\) 的正方形只能往上，\(b\) 的正方形只能往下，所以连边 \((a+n,a),(b,b+n)\)。这样就保证了如果 \(a\) 往下或者 \(b\) 往上，\(a\) 和 \(a+n\) 或 \(b\) 和 \(b+n\) 一定会在一个 SCC 内。
- 如果 \(mid\leq a_x-b_x<2mid\)，那么 \(a\) 往下的时候 \(b\) 必须往下，\(b\) 往上的时候 \(a\) 必须往上。连边 \((a+n,b+n),(b,a)\)。
然后跑 tarjan，判断是否有任意一点 \(a\) 往上和往下的两个点处于同一个 SCC 内即可。
时间复杂度 \(O(n^3\log len)\)，其中 \(len\) 是点坐标值域。三个 \(\log\) 的原因是最坏情况下会有 \(m=n^2\) 条边，而 tarjan 的复杂度是 \(O(n+m)\) 即 \(O(n + n^2)\) 的。
代码
#include <stack>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=210;
int T,n,tot,cnt,head[N],dfn[N],low[N],col[N];
bool vis[N];
stack<int> st;
struct node
{
int x,y;
}a[N];
struct edge
{
int next,to;
}e[N*N*4];
void add(int from,int to)
{
e[++tot].to=to;
e[tot].next=head[from];
head[from]=tot;
}
void tarjan(int x)
{
dfn[x]=low[x]=++tot;
st.push(x); vis[x]=1;
for (int i=head[x];~i;i=e[i].next)
{
int v=e[i].to;
if (!dfn[v])
{
tarjan(v);
low[x]=min(low[x],low[v]);
}
else if (vis[v])
low[x]=min(low[x],dfn[v]);
}
if (dfn[x]==low[x])
{
int y; cnt++;
do {
y=st.top(); st.pop();
vis[y]=0; col[y]=cnt;
} while (x!=y);
}
}
bool check()
{
for (int i=1;i<=n;i++)
if (col[i]==col[i+n]) return 0;
return 1;
}
int binary()
{
int l=1,r=20000,mid;
while (l<=r)
{
mid=(l+r)>>1;
memset(head,-1,sizeof(head));
memset(dfn,0,sizeof(dfn));
memset(col,0,sizeof(col));
tot=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i!=j && abs(a[i].y-a[j].y)<mid && a[i].x<=a[j].x)
{
if (a[i].x==a[j].x)
add(i,j+n),add(i+n,j),add(j,i+n),add(j+n,i);
else if (a[j].x-a[i].x<mid)
add(i+n,i),add(j,j+n);
else if (a[j].x-a[i].x<mid*2)
add(i+n,j+n),add(j,i);
}
tot=cnt=0;
for (int i=1;i<=n*2;i++)
if (!dfn[i]) tarjan(i);
if (check()) l=mid+1;
else r=mid-1;
}
return l-1;
}
int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&a[i].y,&a[i].x);
printf("%d\n",binary());
}
return 0;
}