Hdu 3622(二分+2-SAT)

Hdu 3622
二分后2-SAT判断
1、2-SAT加边视情况加
2、浮点数二分查找的写法
3、浮点数的eps最好开多一点，防卡精度

#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#define ll long long
#define db double
#define ms(i,j) memset(i,j)
#define INF 100000000
#define llINF 1LL<<60
using namespace std;

const int MAXN = (100 + 5) * 2;

struct TwoSat
{
    int mark[MAXN*2];
    int S[MAXN*2];
    vector<int> G[MAXN*2];
    int n, c;

    int init(int ni)
    {
        n = ni;
        for (int i=0;i<=n*2;i++)
        {
            mark[i] = false;
            G[i].clear();
        }
    }
    int dfs(int u)
    {
        if (mark[u^1]) return false;
        if (mark[u]) return true;
        mark[u] = true;
        S[++c] = u;
        for (int i=0;i<G[u].size();i++)
        {
            if (!dfs(G[u][i])) return false;
        }
        return true;
    }
    int solve()
    {
        for (int i=0;i<n*2;i+=2)
        if (!mark[i]&&!mark[i+1])
        {
            c = 0;
            if (!dfs(i))
            {
                while (c>0) mark[S[c--]] = false;
                if (!dfs(i+1)) return false;
            }
        }
        return true;
    }
}ts;

int n;
int xi[MAXN], yi[MAXN];

db dis(int x, int y)
{
    return sqrt(1.0*(xi[x]-xi[y])*(xi[x]-xi[y]) + (yi[x]-yi[y])*(yi[x]-yi[y]));
}
int init()
{
    for (int i=0;i<n;i++)
    {
        scanf("%d%d%d%d", &xi[i], &yi[i], &xi[i+n], &yi[i+n]);
    }
}
int solve()
{
    db l = 0.0, r = 40000.0;
    db ans = 0;
    for (int i=0;i<100;i++)
    {
        db mid = (l+r)/2.0;
        ts.init(n);

        for (int i=0;i<n;i++)
        for (int j=i+1;j<n;j++)
        {
            int x = i*2, y = j*2;
            if (dis(i,j)+0.0000001<mid*2)
            {
                ts.G[x].push_back(y^1);
                ts.G[y].push_back(x^1);
            }
            if (dis(i,j+n)+0.0000001<mid*2)
            {
                ts.G[x].push_back(y);
                ts.G[y^1].push_back(x^1);
            }
            if (dis(i+n,j)+0.0000001<mid*2)
            {
                ts.G[x^1].push_back(y^1);
                ts.G[y].push_back(x);
            }
            if (dis(i+n,j+n)+0.0000001<mid*2)
            {
                ts.G[x^1].push_back(y);
                ts.G[y^1].push_back(x);
            }
        }

        if (ts.solve()) 
        {
            ans = l = mid;
        } else r = mid;
    }
    printf("%.2f\n", ans);
}
int main()
{
    while (scanf("%d", &n)==1)
    {
        init();
        solve();
    }
    return 0;
}