【题意】:给定n组点,每组两个点,要在每组中选一个点安置一个定时炸弹,这个炸弹的范围是以炸弹的位置为圆心的一个圆,半径由你控制。要求安置的n个炸弹不能相互攻击,问最小的圆的半径最大为多少。 

【题解】:很容易想到二分,然后每组有两个点只能选一个,就是一个2sat问题喇。二分答案用2sat判断即可。

【代码】:
  1 #include "iostream"
  2 #include "cstdio"
  3 #include "cstring"
  4 #include "algorithm"
  5 #include "vector"
  6 #include "queue"
  7 #include "cmath"
  8 #include "string"
  9 #include "cctype"
 10 #include "map"
 11 #include "iomanip"
 12 #include "set"
 13 #include "utility"
 14 using namespace std;
 15 typedef pair<intint> pii;
 16 typedef pair<doubledouble> pdd;
 17 #define pb push_back
 18 #define mp make_pair
 19 #define fi first
 20 #define se second
 21 #define sof(x) sizeof(x)
 22 #define lc(x) (x << 1)
 23 #define rc(x) (x << 1 | 1)
 24 #define lowbit(x) (x & (-x))
 25 #define ll long long
 26 #define eps 1e-6
 27 #define maxn 550
 28 int n, nn;
 29 int eh[maxn], tot;
 30 vector<int> vec[maxn];
 31 pdd p[maxn];
 32 
 33 int dfn[maxn], low[maxn], Dindex, instack[maxn], belong[maxn], scc;
 34 int s[maxn], top;
 35 
 36 double getdist(const pdd &a, const pdd &b) {
 37     return sqrt((a.fi - b.fi) * (a.fi - b.fi) + (a.se - b.se) * (a.se - b.se));
 38 }
 39 
 40 void dfs(int u) {
 41     int v;
 42     dfn[u] = low[u] = ++Dindex;
 43     s[++top] = u, instack[u] = true;
 44     int size = vec[u].size();
 45     for(int i = 0; i < size; i++) {
 46         v = vec[u][i];
 47         if(!dfn[v]) dfs(v), low[u] = min(low[u], low[v]);
 48         else if(instack[v]) low[u] = min(low[u], dfn[v]);    
 49      }
 50     if(dfn[u] == low[u]) {
 51         scc++;
 52         do {
 53             v = s[top--];
 54             instack[v] = false;
 55             belong[v] = scc;
 56         }while(v != u);
 57     }
 58 }
 59 
 60 void tarjan() {
 61     top = scc = Dindex = 0;
 62     memset(dfn, 0, sizeof(dfn));
 63     memset(instack, 0, sizeof(instack));
 64     for (int i = 0; i < (nn << 1); i++)
 65         if(!dfn[i]) dfs(i);
 66 }
 67 
 68 bool isOK() {
 69     for(int i = 0; i < nn; i++)
 70         if(belong[i] == belong[i+nn]) return false;
 71     return true;
 72 }
 73 
 74 void build(double limit) {
 75     for(int i = 0; i < (nn << 1); i++) vec[i].clear();
 76     for(int i = 0; i < n; i++) {
 77         int a = i << 1, b = i << 1 | 1;
 78         vec[a].pb(b + nn), vec[b].pb(a + nn);
 79         vec[a+nn].pb(b), vec[b+nn].pb(a);
 80         for(int j = 0; j < i; j++) {
 81             int c = j << 1, d = j << 1 | 1;
 82             if(getdist(p[a], p[c]) + eps < limit) {
 83                 vec[a].pb(c+nn), vec[a].pb(d);
 84                 vec[c].pb(a+nn), vec[c].pb(b);
 85             }
 86             if(getdist(p[a], p[d]) + eps < limit) {
 87                 vec[a].pb(d+nn), vec[a].pb(c);
 88                 vec[d].pb(a+nn), vec[d].pb(b);
 89             }
 90             if(getdist(p[b], p[c]) + eps < limit) {
 91                 vec[b].pb(c+nn), vec[b].pb(d);
 92                 vec[c].pb(b+nn), vec[c].pb(a);
 93             }
 94             if(getdist(p[b], p[d]) + eps < limit) {
 95                 vec[b].pb(d+nn), vec[b].pb(c);
 96                 vec[d].pb(b+nn), vec[d].pb(a);
 97             }
 98         }
 99     }
100 }
101 
102 bool check(double limit) {
103     build(limit);
104     tarjan();
105     return isOK();
106 }
107 
108 void solve() {
109     double l = 0.0, r = 1e6;
110     double ans;
111     while(l + eps < r) {
112         double mid = (l + r) / 2.0;
113         if(check(mid * 2)) ans = mid, l = mid;
114         else r = mid;
115     }
116     printf("%.2f\n", ans);
117 }
118 
119 int main() {
120     while(~scanf("%d", &n)) {
121         nn = n << 1;
122         for(int i = 0; i < nn; i++) scanf("%lf%lf", &p[i].fi, &p[i].se);
123         solve();
124     }
125     return 0;
126 }
127