POJ 2296 Map Labeler / ZOJ 2493 Map Labeler / HIT 2369 Map Labeler / UVAlive 2973 Map Labeler

POJ 2296 Map Labeler / ZOJ 2493 Map Labeler / HIT 2369 Map Labeler / UVAlive 2973 Map Labeler（2-sat 二分）

Description

Map generation is a difficult task in cartography. A vital part of such task is automatic labeling of the cities in a map; where for each city there is text label to be attached to its location, so that no two labels overlap. In this problem, we are concerned with a simple case of automatic map labeling.

Assume that each city is a point on the plane, and its label is a text bounded in a square with edges parallel to x and y axis. The label of each city should be located such that the city point appears exactly in the middle of the top or bottom edges of the label. In a good labeling, the square labels are all of the same size, and no two labels overlap, although they may share one edge. Figure 1 depicts an example of a good labeling (the texts of the labels are not shown.)

Given the coordinates of all city points on the map as integer values, you are to find the maximum label size (an integer value) such that a good labeling exists for the map.

Input

The first line contains a single integer t (1 <= t <= 10), the number of test cases. Each test case starts with a line containing an integer m (3 ≤ m ≤ 100), the number of cities followed by m lines of data each containing a pair of integers; the first integer (X) is the x and the second one (Y) is the y coordinates of one city on the map (-10000 ≤X, Y≤ 10000). Note that no two cities have the same (x, y) coordinates.

Output

The output will be one line per each test case containing the maximum possible label size (an integer value) for a good labeling.

Sample Input

1
6
1 1
2 3
3 2
4 4
10 4
2 5

Sample Output

2

Http

POJ:https://vjudge.net/problem/POJ-2296
ZOJ:https://vjudge.net/problem/ZOJ-2493
HIT:https://vjudge.net/problem/HIT-2369
UVAlive:https://vjudge.net/problem/UVALive-2973

Source

2-sat 二分

题目大意

在平面直角坐标系上有n个点，现在要在这些点之间填充正方形，并且满足每个点都在正方形的上边中点或下边中点。正方形不能重叠，但可以共用一条边。现在要求出满足条件的最大边长正方形的边长。

解决思路

看到这种最小值最大或是最大值最小的题目，立刻能想到二分。所以我们二分边长，然后判断这个边长是否满足题意。

那么现在的关键就是：如何判断某个边长是否，满足题意？

通过读题，我们发现，一个点填充正方形无疑只有两种情况，这个点在正方形的下边中点和在正方形的上边中点。一个点有两种状态，所以我们可以用2-sat来判断可行性。那么我们定义i表示正方形朝上，i+n表示正方形朝下。为了方便起见，在下文中，我们用Diff代表当前要判断的正方形边长。

那么如何建图呢？

我们知道，2-sat中一条有向边i->j表示选i必须选j，那么在这个题中，我们就是要找出两个正方形若一个怎么样另一个必须怎么样。

首先根据简单的推理可得，若两正方形（一下皆用i,j表示，为了方便叙述，我们假定i的纵坐标>=j的纵坐标）横坐标之差>=Diff，或是纵坐标之差>=2*Diff则两个正方形无论怎么摆都不会互相干扰，可以直接跳过。

然后我们分情况讨论：
1.纵坐标相等的时候（yi==yj）

我们发现这时i与j必然要一个向上一个向下。所以我们连接边i->j+n（若i向上则j必须向下），连接边i+n->j（若i向下则j向上），j->i+n，j+n->i（同理）

2.纵坐标之差大于0但小于Diff

这时两个点之间无法摆下一个正方形，所以上面的点必须向上摆，下面的点必须向下摆。

但这样如何连边呢？我们连上i+n->i（i若向下则i必须向上）,j->j+n（j若向上则j必须向下）。这样是不是很奇怪？为什么么会有这样的边出现？没错，这就是刻意制造一种矛盾，使得选i+n时必选i，且在后面判断可行性的时候若i+n与i在同一强连通分量则不符合题意，无解。这里就是用来保证i必须向上，而j必须向下。另外，为了保险起见，还可以连边i->j+n和j+n->i。

3.纵坐标之差大于等于Diff但小于2*Diff

此时，两个点之间是可以摆下一个正方形的，所以有：若上面的向下，则下面的必须向下；若下面的向上，则上面的必须向上（因为最多只能摆下一个正方形）。表述成边就是：i+n->j+n，j->i。

注意此时并不需要连接i->j或是j+n->i+n，因为当上面的向上时，下面的既可以向上也可以向下；同理，下面的向下时，上面的既可以向上也可以向下。

建完图后就是判断可行性了。这里推荐的方法是用Tarjan缩点求强联通分量再看i和i+n是否在同一强连通分量中（若是则说明无解，否则有解）。鉴于前面的博客已经详细讲过如何实现，请到这里查看。

另一种方法是用暴力染色法，前文也已经叙述过了，可以在这里查看。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<vector>
#include<stack>
#include<cmath>
using namespace std;

#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=500;
const int inf=2147483647;

int n;
int Readx[maxN];//读入
int Ready[maxN];
vector<int> E[maxN];//存下2-sat图
//tajan  //Tarjan算法要用到的变量，不多说
int cnt;
int dfn[maxN];
int low[maxN];
bool instack[maxN];
stack<int> S;
//LTK  //强连通分量
int LTKcnt;
int Belong[maxN];//原图中的每个点所属的强连通分量编号

void init();
void Graph_init(int Diff);
void Link(int u,int v);
bool check();
void tarjan(int u);

int main()
{
    int T;
    cin>>T;
    for (int ti=1;ti<=T;ti++)
    {
        cin>>n;
        init();
        for (int i=1;i<=n;i++)
            scanf("%d%d",&Readx[i],&Ready[i]);
        int l=0,r=20000;
        int Ans;
        do//二分答案
        {
            init();
            int mid=(l+r)/2;
            Graph_init(mid);//每次检查前都要重新初始化
            if (check())//检查Mid是否满足
            {
                Ans=mid;
                l=mid+1;
            }
            else
                r=mid;
        }
        while (l<r);
        cout<<Ans<<endl;
    }
    return 0;
}

void init()
{
    cnt=LTKcnt=0;
    mem(dfn,0);
    mem(instack,0);
    for (int i=0;i<=n*2;i++)
        E[i].clear();
    while (!S.empty())
        S.pop();
    return;
}
void Graph_init(int Diff)
{
    for (int i=1;i<=n;i++)
        for (int j=i+1;j<=n;j++)
            if (abs(Readx[i]-Readx[j])<Diff)//i表示往上，i+n表示往下
            {
                int maxy,miny;
                if (Ready[i]>Ready[j])
                {
                    maxy=i;
                    miny=j;
                }
                else
                {
                    maxy=j;
                    miny=i;
                }
                if (Ready[maxy]==Ready[miny])//纵坐标相同时，必有一上一下
                {
                    Link(miny,maxy+n);//如果下面的往上，上面的的必须往下
                    Link(maxy,miny+n);//如果上面的往上，下面的的必须往下
                    Link(miny+n,maxy);//同理
                    Link(maxy+n,miny);
                    continue;
                }
                if ((Ready[maxy]-Ready[miny]<2*Diff)&&(Ready[maxy]-Ready[miny]>=Diff))
                {
                    Link(miny,maxy);//如果下面的往上，上面的必须往上
                    Link(maxy+n,miny+n);//如果上面的往下，下面的必须往下
                    continue;
                }
                if ((Ready[maxy]-Ready[miny]<Diff))
                {
                    Link(miny,miny+n);//下面的必须往下
                    Link(maxy+n,maxy);//上面的必须往上
                    Link(miny+n,maxy);//下面的必须往下，上面的必须往上
                    Link(maxy,miny+n);//上面的必须往上，下面的必须往下
                }
            }
    return;
}

void Link(int u,int v)
{
    E[u].push_back(v);
    return;
}

bool check()
{
    for (int i=1;i<=2*n;i++)
        if (dfn[i]==0)
        {
            tarjan(i);
        }
    for (int i=1;i<=n;i++)
        if (Belong[i]==Belong[i+n])//如果i与i+n在同一强连通分量则说明矛盾（一个正方形不可能又往上又往下）
            return 0;
    return 1;
}

void tarjan(int u)//经典的Tarjan过程
{
    int v;

    cnt++;
    dfn[u]=low[u]=cnt;
    instack[u]=1;
    S.push(u);

    for (int i=0;i<E[u].size();i++)
    {
        v=E[u][i];
        if (dfn[v]==0)
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else
            if (instack[v]==1)
                low[u]=min(low[u],dfn[v]);
    }
    if (dfn[u]==low[u])
    {
        LTKcnt++;
        do
        {
            v=S.top();
            S.pop();
            instack[v]=0;
            Belong[v]=LTKcnt;
        }
        while (u!=v);
    }
    return;
}