1. 首页
2. 2-SAT
3. 本页

UVALive 7425 Cleaning Pipes (2-sat)

题意：~

思路：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
typedef pair<int, int> PI;

const int MAXN = 10020;
const int MAXM = 5000010;
struct Edge
{
    int to,next;
}edge[MAXM];
int head[MAXN],tot;
void init()
{
    tot = 0;
    memset(head,-1,sizeof(head));
}
void addedge(int u,int v)
{
    edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++;
}
bool vis[MAXN];
int S[MAXN],top;
bool dfs(int u)
{
    if(vis[u^1])return false;
    if(vis[u])return true;
    vis[u] = true;
    S[top++] = u;
    for(int i = head[u];i != -1;i = edge[i].next)
        if(!dfs(edge[i].to))
        return false;
    return true;
}
bool Twosat(int n)
{
    memset(vis,false,sizeof(vis));
    for(int i = 0;i < n;i += 2)
    {
        if(vis[i] || vis[i^1]) continue;
        top = 0;
        if(!dfs(i))
        {
            while(top)vis[S[--top]] = false;
            if(!dfs(i^1)) return false;
        }
    }
    return true;
}

#define eps 1e-8
#define zero(x) (((x)>0?(x):-(x))<eps)
int co[1005];
vector<int> eg[1005];

struct point
{
    double x, y;
} nd[1005];

struct line
{
    point a, b;
    int id;
} li[1005];

double xmult(point p1, point p2, point p0)
{
    return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
}

int dots_inline(point p1, point p2, point p3)
{
    return zero(xmult(p1, p2, p3));
}

int dot_online_in(point p, point l1, point l2)
{
    return zero(xmult(p, l1, l2)) && (l1.x - p.x) * (l2.x - p.x) < eps && (l1.y - p.y) * (l2.y - p.y) < eps;
}

int same_side(point p1, point p2, point l1, point l2)
{
    return xmult(l1, p1, l2) * xmult(l1, p2, l2) > eps;
}

int intersect_in(point u1, point u2, point v1, point v2)
{
    if (!dots_inline(u1, u2, v1) || !dots_inline(u1, u2, v2))
        return !same_side(u1, u2, v1, v2) && !same_side(v1, v2, u1, u2);
    return
    dot_online_in(u1, v1, v2) || dot_online_in(u2, v1, v2) || dot_online_in(v1, u1, u2) || dot_online_in(v2, u1, u2);
}


int main()
{
    int n, m;
    while(~scanf("%d%d", &n, &m))
    {
        init();
        for(int i = 1; i <= n; i++)
        {
            eg[i].clear();
            co[i] = 0;
        }
        for(int i = 1; i <= n; i++) scanf("%lf%lf", &nd[i].x, &nd[i].y);
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%lf%lf", &li[i].id, &li[i].b.x, &li[i].b.y);
            li[i].a = nd[li[i].id];
        }
        for(int i = 1; i <= m; i++)
        {
            for(int j = i + 1; j <= m; j++)
            {
                if(li[i].id == li[j].id)
                    continue;
                if(intersect_in(li[i].a, li[i].b, li[j].a, li[j].b))
                {
                    int u = i - 1, v = j - 1;
                    u *= 2, v *= 2;
                    addedge(u, v ^ 1);
                    addedge(v, u ^ 1);
                    addedge(u ^ 1, v);
                    addedge(v ^ 1, u);
                }
            }
        }
        if(Twosat(2 * m)) puts("possible");
        else puts("impossible");
    }
    return 0;
}
/*
2 3
0 0
0 10
1 5 15
1 2 15
2 10 10

*/