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

【题目链接】

http://poj.org/problem?id=2296

【题目大意】

坐标轴上有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\n", ans);
    }
    return 0;
}