Time Limit: 10000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5396 Accepted Submission(s): 1925
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
typedef pair<int, int> pii;
typedef long long LL;
const double PI = acos(-1.0);
const double eps = 1e-5;
const int N = 110;
const int M = N * N * 4;
struct edge
{
int to, nxt;
edge() {}
edge(int _to, int _nxt): to(_to), nxt(_nxt) {}
};
pii P[N];
edge E[M];
int head[N << 1], tot;
int dfn[N << 1], low[N << 1], st[N << 1], belong[N << 1], ts, scc, top;
bitset < N << 1 > ins;
int n;
void init()
{
CLR(head, -1);
tot = 0;
CLR(dfn, 0);
CLR(low, 0);
CLR(belong, 0);
ts = scc = top = 0;
ins.reset();
}
inline void add(int s, int t)
{
E[tot] = edge(t, head[s]);
head[s] = tot++;
}
void Tarjan(int u)
{
dfn[u] = low[u] = ++ts;
st[top++] = u;
ins[u] = 1;
int i, v;
for (i = head[u]; ~i; i = E[i].nxt)
{
v = E[i].to;
if (!dfn[v])
{
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (ins[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
++scc;
do
{
v = st[--top];
ins[v] = 0;
belong[v] = scc;
}
while (u != v);
}
}
inline double cal(const pii &a, const pii &b)
{
return sqrt((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second));
}
bool check(double r, int sz)
{
init();
int i, j;
for (i = 0; i < sz; i += 2)
{
for (j = i + 2; j < sz; ++j)
{
double dx = cal(P[i], P[j]);
if (dx < 2 * r)
{
add(i, j ^ 1);
add(j, i ^ 1);
}
}
}
for (i = 1; i < sz; i += 2)
{
for (j = i + 1; j < sz; ++j)
{
double dx = cal(P[i], P[j]);
if (dx < 2 * r)
{
add(i, j ^ 1);
add(j, i ^ 1);
}
}
}
for (i = 0; i < sz; ++i)
if (!dfn[i])
Tarjan(i);
for (i = 0; i < sz; ++i)
if (belong[i] == belong[i ^ 1])
return false;
return true;
}
int main(void)
{
int i;
while (~scanf("%d", &n))
{
for (i = 0; i < (n << 1); i += 2)
scanf("%d%d%d%d", &P[i].first, &P[i].second, &P[i | 1].first, &P[i | 1].second);
double L = 0, R = 10000 * 1.45;
double ans = 0;
while (R - L >= eps)
{
double mid = (L + R) / 2.0;
if (check(mid, n << 1))
{
L = mid;
ans = mid;
}
else
R = mid;
}
printf("%.2f\n", ans);
}
return 0;
}
原文:http://www.cnblogs.com/Blackops/p/6443077.html