POJ2296 Map Labeler

Map Labeler

Time Limit: 1000MS Memory Limit: 65536K

Total Submissions: 1659 Accepted: 540

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
Source

Tehran 2003

题意：一个平面直角坐标系里有m个点，要求使这些点每一个都在一个具有一定长度的正方形的上边或下边（正方形不能重合，边界可以重叠），求这个正方形的最大边长。

2-SAT，二分边长，然后按二分的值建图。

1代表这个点放在上边界，1'代表放在下边界

如果x1-x2>=2*mid，continue。。两个矩形不管怎么放都不会重合。

abs(y1-y2)>=2*mid，continue..同上。

y1-y2=0....两个点在与x轴平行的同一条直线上，所以1在上边界，2就肯定不能再上边界，所以1-2',2'-1,1'-2,2-1'。。

下面假设y1大于y2.。。。

y1-y2<mid...1只能在下边界上，2只能在上边界上。。1-1',2'-2..

mid<=y1-y2<2*mid。。如果1在上边界，那么2也只能在上边界。。1-2,1'-2'。。

以上都可以自己动手画下图。。就很好理解了。。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<cmath>
using namespace std;
const int MAXN=210;
const int MAXE=40010;
int head[MAXN],size;
struct EDGE
{
    int v,next;
}edge[MAXE];
struct Node
{
    int x,y;
}p[MAXN];
int sccno[MAXN],low[MAXN],pre[MAXN],dfs_clock,sc_cnt,n;
stack<int> S;
void init()
{
    memset(head,-1,sizeof(head));
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    size=dfs_clock=sc_cnt=0;
}
void add_edge(int u,int v)
{
    edge[size].v=v;
    edge[size].next=head[u];
    head[u]=size++;
}
void tarjan(int u)
{
    pre[u]=low[u]=++dfs_clock;
    S.push(u);
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(!pre[v])
        {
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccno[v])
        {
            low[u]=min(low[u],pre[v]);
        }
    }
    if(low[u]==pre[u])
    {
        sc_cnt++;
        while(1)
        {
            int x=S.top();
            S.pop();
            sccno[x]=sc_cnt;
            if(x==u)
                break;
        }
    }
}
void build(int mid)
{
    init();
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(abs(p[i].x-p[j].x)>=mid)
                continue;
            if(abs(p[i].y-p[j].y)>=2*mid)
                continue;
            if(p[i].y-p[j].y==0)
            {
                add_edge(i<<1,j<<1|1);
                add_edge(i<<1|1,j<<1);
                add_edge(j<<1|1,i<<1);
                add_edge(j<<1,i<<1|1);
                continue;
            }
            if(p[i].y>p[j].y)
            {
                if(p[i].y-p[j].y>=mid)
                {
                    add_edge(i<<1,j<<1);
                    add_edge(j<<1|1,i<<1|1);
                }
                else if(p[i].y-p[j].y<mid)
                {
                    add_edge(i<<1,i<<1|1);
                    add_edge(j<<1|1,j<<1);
                }
            }
            else
            {
                if(p[j].y-p[i].y>=mid)
                {
                    add_edge(j<<1,i<<1);
                    add_edge(i<<1|1,j<<1|1);
                }
                else if(p[j].y-p[i].y<mid)
                {
                    add_edge(j<<1,j<<1|1);
                    add_edge(i<<1|1,i<<1);
                }
            }
        }
    }
}
bool test()
{
    int i;
    for(i=0;i<2*n;i++)
        if(!pre[i])
        tarjan(i);
    for(i=0;i<n;i++)
        if(sccno[i<<1]==sccno[i<<1|1])
        return 0;
    return 1;
}
int main()
{
    int t,i;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        for(i=0;i<n;i++)
            scanf("%d%d",&p[i].x,&p[i].y);
        int l=0,r=20000;
        int ans=0;
        while(l<=r)
        {
            int mid=(l+r)>>1;
            build(mid);
            if(test())
            {
                ans=mid;
                l=mid+1;
            }
            else
                r=mid-1;
        }
        printf("%d\n",ans);
    }
    return 0;
}