题目大意：玩一个放炸弹游戏，有N次放炸弹的机会，每次放炸弹时，你都有两个位置可以选择，问如何放炸弹，能使爆炸的炸弹的半径的最小值最大(炸弹爆炸半径可以控制，但是爆炸形成的圈不能有重叠部分)

解题思路：最小值最大，二分
二分半径，如果有不满足的点，就建立起限制边，接着判断能否完成染色即可

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define esp 1e-5 #define N 210 struct Node { int x, y; }node[N][2]; bool mark[N]; vector
        
          G[N]; int top, n, m; int S[N]; void init (){ for (int i = 0; i < n ; i++) { scanf(%d%d%d%d, &node[i][0].x, &node[i][0].y, &node[i][1].x, &node[i][1].y); } } double distance(int i, int a, int j, int b) { return sqrt( 1.0 * (node[i][a].x - node[j][b].x) * (node[i][a].x - node[j][b].x) + 1.0 * (node[i][a].y - node[j][b].y) * (node[i][a].y - node[j][b].y)); } void AddEdge(int i, int a, int j, int b) { int x = i * 2 + a; int y = j * 2 + b; G[x ^ 1].push_back(y); G[y ^ 1].push_back(x); } bool dfs(int u) { if (mark[u ^ 1]) return false; if (mark[u]) return true; mark[u] = true; S[++top] = u; for (int i = 0; i < G[u].size(); i++) if (!dfs(G[u][i])) return false; return true; } bool judge(double mid) { for (int i = 0; i < 2 * n; i++) G[i].clear(); for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int a = 0; a < 2; a++) for (int b = 0; b < 2; b++) { //printf(dis is %lf , distance(i, a, j, b)); if (2 * mid - distance(i, a, j, b) > esp) { AddEdge(i, a, j, b); } } } } memset(mark, 0, sizeof(mark)); for (int i = 0; i < 2 * n; i += 2) { if (!mark[i] && !mark[i ^ 1]) { top = 0; if (!dfs(i)) { while(top) mark[S[top--]] = false; if (!dfs(i ^ 1)) return false; } } } return true; } void solve() { double l = 0, r = 1e5; for (int i = 0; i < 30; i++) { double mid = (l + r) / 2; // printf(l is %lf r is %lf mid is %lf , l, r, mid); if (judge(mid)) l = mid; else r = mid; } printf(%.2lf , l); } int main() { while (scanf(%d, &n) != EOF) { init(); solve(); } return 0; } 
        
       
      
     
    
   

?