POJ2296二分2sat

题意：

给n个点，每个点必须在一个正方形上，可以在正方向上面边的中点或者是下面边的中点，正方形是和x,y轴平行的，而且所有的点的正方形的边长一样，并且正方形不能相互重叠（边相邻可以），问满足这个要求的正方形的最大边长是多少？

思路：

点的个数最少是3，所以不存在无穷大的情况，每个点的正方形有两种选择，所以是两种中选一种，每两个点中可能存在某种选择和某种选择冲突的情况，那么好办了，是不是就是夫妻参加晚会只能去一个但是一些人之间有矛盾不能同时去的变形？直接就是2-sat，至于答案是输出最大的边长，这个好办，直接二分边长，然后每一步都是2-sat判断是否可行就ok了。

#include<stack>

#include<stdio.h>

#include<string.h>

#define N_node 200 + 10

#define N_edge 100000 + 100

using namespace std;

typedef struct

{

    int to ,next;

}STAR;

typedef struct

{

    double x ,y;

}NODE;

NODE node[N_node];

STAR E1[N_edge] ,E2[N_edge];

int list1[N_node] ,list2[N_node] ,tot;

int Belong[N_node] ,mark[N_node] ,CNT;

stack<int>mysk;

void add(int a ,int b)

{

    E1[++tot].to = b;

    E1[tot].next = list1[a];

    list1[a] = tot;

    E2[tot].to = a;

    E2[tot].next = list2[b];

    list2[b] = tot;

}

void DFS1(int s)

{

    mark[s] = 1;

    for(int k = list1[s] ;k ;k = E1[k].next)

    {

        int to = E1[k].to;

        if(!mark[to]) DFS1(to);

    }

    mysk.push(s);

}

void DFS2(int s)

{

    Belong[s] = CNT;

    mark[s] = 1;

    for(int k = list2[s] ;k ;k = E2[k].next)

    {

        int to = E2[k].to;

        if(!mark[to]) DFS2(to);

    }

}

double minn(double x ,double y)

{

    return x < y ? x : y;

}

double maxx(double x ,double y)

{

    return x > y ? x : y;

}

bool jude(NODE a ,NODE b ,double l)

{

    double s ,x ,z ,y;

    s = minn(a.y + l ,b.y + l);

    y = minn(a.x + l ,b.x + l);

    x = maxx(a.y ,b.y);

    z = maxx(a.x ,b.x);

    return s > x && y > z;

}

bool J(int n ,int nowl)

{

    int i ,j ,a1 ,a2 ,b1 ,b2;

    NODE t1 ,t2;

    double r = nowl * 1.0 / 2;

    memset(list1 ,0 ,sizeof(list1));

    memset(list2 ,0 ,sizeof(list2));

    tot = 1;

    for(i = 1 ;i <= n ;i ++)

    for(j = i + 1 ;j <= n ;j ++)

    {

        a1 = i * 2 ,b1 = i * 2 + 1;

        a2 = j * 2 ,b2 = j * 2 + 1;

        //上上

        t1.x = node[i].x - r ,t1.y = node[i].y;

        t2.x = node[j].x - r ,t2.y = node[j].y;

        if(jude(t1 ,t2 ,nowl * 1.0)) add(a1 ,a2 ^ 1) ,add(a2 ,a1 ^ 1);

        //上下

        t1.x = node[i].x - r ,t1.y = node[i].y;

        t2.x = node[j].x - r ,t2.y = node[j].y - r * 2;

        if(jude(t1 ,t2 ,nowl * 1.0)) add(a1 ,b2 ^ 1) ,add(b2 ,a1 ^ 1);

        //下上

        t1.x = node[i].x - r ,t1.y = node[i].y - r * 2;

        t2.x = node[j].x - r ,t2.y = node[j].y;

        if(jude(t1 ,t2 ,nowl * 1.0)) add(b1 ,a2 ^ 1) ,add(a2 ,b1 ^ 1);

        //下下

        t1.x = node[i].x - r ,t1.y = node[i].y - r * 2;

        t2.x = node[j].x - r ,t2.y = node[j].y - r * 2;

        if(jude(t1 ,t2 ,nowl * 1.0)) add(b1 ,b2 ^ 1) ,add(b2 ,b1 ^ 1);

    }

    memset(mark ,0 ,sizeof(mark));

    while(!mysk.empty()) mysk.pop();

    n *= 2;

    for(i = 1 ;i <= n ;i ++)

    if(!mark[i]) DFS1(i);

    CNT = 0;

    memset(mark ,0 ,sizeof(mark));

    while(!mysk.empty())

    {

        int xin = mysk.top();

        mysk.pop();

        if(mark[xin]) continue;

        CNT ++;

        DFS2(xin);

    }

    int mk = 0;

    for(i = 1 ;i <= n ;i += 2)

    if(Belong[i] == Belong[i^1])

    {

        mk = 1;

        break;

    }

    return !mk;

}

int main ()

{

    int t ,n ,i ,j;

    scanf("%d" ,&t);

    while(t--)

    {

        scanf("%d" ,&n);

        for(i = 1 ;i <= n ;i ++)

        scanf("%lf %lf" ,&node[i].x ,&node[i].y);

        int low = 0 ,up = 20000 + 100 ,mid ,ans = 0;

        while(low <= up)

        {

            mid = (low + up) >> 1;

            if(J(n ,mid)) ans = mid ,low = mid + 1;

            else up = mid - 1;

        }

        printf("%d\n" ,ans);

    }

    return 0;

}

巴特西

POJ2296二分2sat

最新文章

热门文章