思路：二分答案，然后建图，用2-SAT判断方案是否可行。

#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;
double r;
const double eps=1e-5;
const int MAXN = 110;
struct twosat
{  
    int n,c;  
    vector<int> g[MAXN<<1];  
    bool mark[MAXN<<1];  
    int s[MAXN<<1];  
    
	bool dfs(int x) 
	{  
		int i;
        if (mark[x^1]) 
			return 0;  
        if (mark[x]) 
			return 1;  
        mark[x] = 1;  
        s[c++] = x;  
        for (i = 0; i < g[x].size(); i++)  
            if (!dfs(g[x][i])) 
				return 0;  
        return 1;  
    }  
    
    void init(int n) 
	{  
		int i,t=n<<1;
        this->n = n;  
        for (i = 0; i < t; i++)   
            g[i].clear();  
        memset(mark, 0, sizeof(mark));  
    }  
  
    void add_clause(int x, int xval, int y, int yval) 
	{  
        x = x * 2 + xval;  
        y = y * 2 + yval;  
        g[x^1].push_back(y);  
        g[y^1].push_back(x);  
    }  
  
    bool solve() 
	{  
		int i,t=n<<1;
        for (i = 0; i < t; i += 2)   
            if (!mark[i] && !mark[i + 1]) 
			{  
                c = 0;  
                if (!dfs(i)) 
				{  
                    while (c > 0) 
						mark[s[--c]] =0;   
                    if (!dfs(i + 1)) 
						return 0;  
                }  
            }
        return 1;  
    }  
}woker;  
struct point
{
	double x,y;
	double dis(point a)
	{
		return sqrt(pow(x-a.x,2)+pow(y-a.y,2));
	}
}in[110][2];
bool isok(point a,point b)
{
	return !(a.dis(b)>2*r);
}
void create(int n)
{
	int i,j,x,y;
	woker.init(n);
	for(i=0;i<n;i++)
		for(j=i+1;j<n;j++)
			for(x=0;x<2;x++)
				for(y=0;y<2;y++)
					if(isok(in[i][x],in[j][y]))
						woker.add_clause(i,x,j,y);
}
int main()
{
	int i,j,n;
	double low,high;
	while(cin>>n)
	{
		for(i=0;i<n;i++)
			for(j=0;j<2;j++)
				cin>>in[i][j].x>>in[i][j].y;
		low=0;
		high=1e5;
		while(high-low>eps)
		{
			r=(high+low)/2;
			create(n);
			if(woker.solve())
				low=r;
			else
				high=r;
		}
		printf("%.2f\n",low);
	}
	return 0;
}

Bomb Game

2
1 1 1 -1
-1 -1 -1 1
2
1 1 -1 -1
1 -1 -1 1

1.41
1.00

hdu 3622 Bomb Game

原文：http://blog.csdn.net/stl112514/article/details/41596631