poj 2296 Map Labeler【二分+2-set】【经典】

谁践踏了优雅 2022-08-08 12:56 103阅读 0赞

题目：[poj 2296 Map Labeler][]

题意：给出以下二维坐标点，然后让你往平面上放正方形，点必须落在正方形上面边的中点或者下面边的中点，正方形不能重叠，可以共用边。问最大正方形边的边长。

分析：这种最大化最小值或者最小化最大值的问题，我们都可以种二分+判断的方法来解，这个也不例外，关键是判断部分  
我们现在二分枚举边长为diff，然后所有的点就变成了在正方形上面或者下面的问题了，二选一的问题很明显可以用2-set来判断的  
这个题目的关键在于理解他们之间的二元关系并建图，下面我们来分析

首先，对于一个点a，在正方形的上边上，设为点a，在下边上设为点-a。  
b同样的，上边上设为点b，下边上设为-b  
对于任意两个点a和b  
如果**a和b的横坐标只差小于diff**  
如果**纵坐标值相等**，那么只能是一个在上面一个在下面，表示而二元关系为（a | b）即a和b只能有一个在上边上，改写成等价形式  
（a&-b）|（-a&b）即a在上边则b必然在下边，a在下边的话b必然在上边，我们在加边的时候要求强连通分量，所以这里可以按无向边建图。  
如果**纵坐标的值小于diff**，则纵坐标值大的所在正方形必然位于上面，小的位于下面，我们假设a的纵坐标大于b，我们可以让a–>-a,-b–>b,为什么呢？因为我们必然要让a的四边形位于上面，即点在下边上，这样连边如果点在上边，则会形成a个-a属于同一个强连通分量导致可行，so..  
如果**纵坐标的值小于2\*diff**，同样假设a纵坐标的大于b，那么a的四边形在下，则b的必然在下，b的在上则a的必然也在上所以-a–>-b,b–>a  
这用只要同s-set跑是否可行就ok  
对其中的一些关系的建图还是很经典的。  
AC代码：

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <algorithm>
    #include <stack>
    using namespace std;
    const int N = 2200;
    
    struct TwoSet
    {
        int dfs_clock,tpnum;
        stack<int> sta;
        vector<int> G[2*N];
        bool vis[2*N];
        int dfn[2*N],low[2*N],tp[2*N];
        void init(int n)
        {
            for(int i=0; i<=2*n; i++)
                G[i].clear();
            dfs_clock = tpnum = 0;
            memset(vis,false,sizeof(vis));
            memset(dfn,0,sizeof(dfn));
            memset(low,0,sizeof(low));
            memset(tp,0,sizeof(tp));
            while(!sta.empty())
                sta.pop();
    
        }
        void add(int x,int y)
        {
            G[x].push_back(y);
        }
        void add_Node(int x,int y)
        {
            add(x,y+1);
            add(x+1,y);
            add(y+1,x);
            add(y,x+1);
        }
        void Tarjan(int x)
        {
            sta.push(x);
            vis[x] = true;
            dfn[x] = low[x] = ++dfs_clock;
            for(int i=0; i<G[x].size(); i++)
            {
                int y = G[x][i];
                if(!dfn[y])
                {
                    Tarjan(y);
                    low[x] = min(low[x],low[y]);
                }
                else
                {
                    if(vis[y])
                        low[x] = min(low[x],dfn[y]);
                }
            }
            if(low[x] == dfn[x])
            {
                tpnum++;
                do
                {
                    x = sta.top();
                    sta.pop();
                    vis[x] = false;
                    tp[x] = tpnum;
                }
                while(low[x] != dfn[x]);
            }
        }
        bool yougth(int n)
        {
            for(int i=0; i<2*n; i++)
                if(!dfn[i])
                    Tarjan(i);
            for(int i=0; i<n; i++)
                if(tp[i]==tp[i+n])
                    return false;
            return true;
        }
    };
    TwoSet solver;
    struct Node
    {
        int x,y;
    };
    Node re[N];
    
    bool test(int diff,int n)
    {
        solver.init(n);
        for(int i=0; i<n; i++)
        {
            for(int j=i+1; j<n; j++)
            {
                if(abs(re[i].x-re[j].x)<diff)
                {
                    if(re[i].y==re[j].y)
                        solver.add(i,j+n),solver.add(j,i+n),solver.add(j+n,i),solver.add(i+n,j);
                    else if(re[i].y>re[j].y&&(re[i].y-re[j].y<diff))
                        solver.add(i,i+n),solver.add(j+n,j);
                    else if(re[j].y>re[i].y&&(re[j].y-re[i].y<diff))
                        solver.add(j,j+n),solver.add(i+n,i);
                    else if(re[i].y>re[j].y&&(re[i].y-re[j].y)<2*diff)
                        solver.add(i,j),solver.add(j+n,i+n);
                    else if(re[j].y>re[i].y&&(re[j].y-re[i].y)<2*diff)
                        solver.add(j,i),solver.add(i+n,j+n);
                }
            }
        }
        return solver.yougth(n);
    }
    
    int main()
    {
    //    freopen("Input.txt","r",stdin);
        int cas,n;
        scanf("%d",&cas);
        while(cas--)
        {
            scanf("%d",&n);
            for(int i=0; i<n; i++)
                scanf("%d%d",&re[i].x,&re[i].y);
            int l = 0,r = 0x3f3f3f3f,mid;
            int ans = -1;
            while(l<=r)
            {
                solver.init(n);
                mid = (l+r)>>1;
                if(test(mid,n))
                    ans = mid,l = mid+1;
                else r = mid-1;
            }
            printf("%d\n",ans);
        }
        return 0;
    }

[poj 2296 Map Labeler]: http://poj.org/problem?id=2296