题意:
在平面上给n个点,要在以每个点为中心向上或向下画一个边长为L的正方形,要保证这些正方形不能重叠,求可画正方形边长的最大值。
分析:
对于每个点,有向上或向下画两种状态,根据这个可以用2-sat建模。
代码:
//poj 2296
//sep9
#include <iostream>
#include <vector>
using namespace std;
const int maxN=300;
const int maxL=30000;
vector<int> g[maxN],ng[maxN];
int n,m,cnt,scc,vis[maxN],dfn[maxN];
int x[maxN],y[maxN];void addegde(int u,int v)
{g[u].push_back(v);ng[v].push_back(u);
}void dfs(int k)
{vis[k]=1;for(int i=g[k].size()-1;i>=0;--i)if(!vis[g[k][i]])dfs(g[k][i]);dfn[++cnt]=k;
}void ndfs(int k)
{vis[k]=scc;for(int i=ng[k].size()-1;i>=0;--i)if(!vis[ng[k][i]])ndfs(ng[k][i]);
}
void kosaraju()
{memset(vis,0,sizeof(vis));cnt=0;for(int i=1;i<=2*n;++i)if(!vis[i])dfs(i); memset(vis,0,sizeof(vis));scc=0;for(int i=2*n;i>=1;--i)if(!vis[dfn[i]]){++scc;ndfs(dfn[i]);}
}int two_sat(int L)
{int i,j;for(i=1;i<=2*n;++i)g[i].clear(),ng[i].clear();for(i=1;i<=n;++i)for(j=i+1;j<=n;++j){int x1,y1,x2,y2,dx,dy;x1=x[i],y1=y[i],x2=x[j],y2=y[j];dx=abs(x1-x2);dy=abs(y1-y2);if(dx>=L) continue;else if(dy>=2*L) continue;else{if(y2>y1){if(y2-y1<L){addegde(j,j+n);addegde(i+n,i);}else if(y2-y1>=L)addegde(i+n,j+n); addegde(j,i);}else if(y2==y1){addegde(i,j+n);addegde(i+n,j);addegde(j,i+n);addegde(j+n,i);}else if(y2<y1){if(y1-y2<L){addegde(j+n,j);addegde(i,i+n);}else if(y1-y2>=L){addegde(i,j);addegde(j+n,i+n);}}}}kosaraju();for(i=1;i<=n;++i)if(vis[i]==vis[i+n])return 0; return 1;
}int main()
{int i,j,cases;scanf("%d",&cases);while(cases--){scanf("%d",&n);for(i=1;i<=n;++i)scanf("%d%d",&x[i],&y[i]);int l=0,r=maxL,ans=0; while(l<r){int mid=(l+r)/2;if(two_sat(mid)==0)r=mid;elsel=mid+1,ans=mid;}printf("%d\n",ans); }return 0;
}