算法：POJ 2296 Map Labeler（2-SAT+二分）

算法：POJ 2296 Map Labeler（2-SAT+二分）2014-01-10 csdn shuangde800【题目大意】

坐标轴上有N个点，要在每个点上贴一个正方形，这个正方形的横竖边分别和x，y 轴平行，并且要使得点要么在正方形的上面那条边的中点，或者在下面那条边的中点，并且任意两个点的正方形都不重叠（可以重边）。问正方形最大边长可以多少？

【思路】

可以很容易的看出，正方形要么在点的上方，要么在下方，所以是用2-SAT来判断的，关键是加边的判断，要涉及到两个正方形的位置的重叠关系比较麻烦。

然后二分正方形的边长即可。

【代码】

#include<iostream>#include<queue>#include<cstdio>#include<cstring>using namespace std;const int MAXN = 110;const int VN = MAXN*2;const int EN = VN*VN*2*10;const int INF= 0x3f3f3f3f;int n;int Abs（int n）{return n<0？-n:n;}struct Node{int x, y;}arr[MAXN];struct Graph{int size, head[VN];struct{int v, next; }E[EN];void init（）{size=0; memset（head, -1, sizeof（head））; };void addEdge（int u, int v）{E[size].v = v;E[size].next = head[u];head[u] = size++;}}g;class Two_Sat{public:bool check（const Graph& g, const int n）{scc（g, 2*n）;for（int i=0; i<n; ++i）if（belong[i] == belong[i+n]）return false;return true;}private:void tarjan（const Graph& g, const int u）{int v;dfn[u] = low[u] = ++idx;sta[top++] = u;instack[u] = true;for（int e=g.head[u]; e！=-1; e=g.E[e].next）{v = g.E[e].v;if（dfn[v] == -1）{tarjan（g, v）;low[u] = min（low[u], low[v]）;}else if（instack[v]）{low[u] = min（low[u], dfn[v]）; }}if（dfn[u] == low[u]）{++bcnt;do{v = sta[--top];instack[v] = false;belong[v] = bcnt;}while（u ！= v）;}}void scc（const Graph& g, const int n）{idx = top = bcnt = 0;memset（dfn, -1, sizeof（dfn））;memset（instack, 0, sizeof（instack））;for（int i=0; i<n; ++i）{if（dfn[i] == -1）tarjan（g, i）;}}private:int idx, top, bcnt;int dfn[VN], low[VN], sta[VN], belong[VN];bool instack[VN];}sat;void buildGraph（int r）{g.init（）;for（int i=0; i<n; ++i）{for（int j=i+1; j<n; ++j）{if（Abs（arr[i].x-arr[j].x） >= r） continue;if（Abs（arr[i].y-arr[j].y） >= 2*r） continue;if（Abs（arr[i].y-arr[j].y） < r）{if（arr[i].y > arr[j].y）{ // i在上面g.addEdge（i, j+n）;g.addEdge（i+n, i）;g.addEdge（j, j+n）;g.addEdge（j+n, i）;}else if（arr[i].y < arr[j].y）{g.addEdge（j, i+n）;g.addEdge（j+n, j）;g.addEdge（i, i+n）;g.addEdge（i+n, j）;}else{g.addEdge（i, j+n）;g.addEdge（i+n, j）;g.addEdge（j, i+n）;g.addEdge（j+n, i）;}}else{if（arr[i].y > arr[j].y）{g.addEdge（i+n, j+n）;g.addEdge（j, i）;}else{g.addEdge（j+n, i+n）;g.addEdge（i, j）;}}}}}int main（）{int nCase;scanf（"%d", &nCase）;while（nCase--）{scanf（"%d", &n）;for（int i=0; i<n; ++i）scanf（"%d%d", &arr[i].x, &arr[i].y）;int l=0;int r=20000, m;int ans=0; while（l < r）{ // 二分边长m = （l+r）>>1;buildGraph（m）;if（sat.check（g, n））{ans = m;l=m+1;} else r=m;}printf（"%d
", ans）;}return 0;}