记录编号	32698	评测结果	AAAAAAAAAA
题目名称	燃烧	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2011-11-07 19:32:18	内存使用	0.64 MiB

#include <cstdio>
#include <cstdlib>
#include <cmath>
int n, p, p1, p2, p3;
double s, m, v, u;
double c[1010][3], g[201][201], l[1010][6];
inline double max(double a, double b) {
    return a>b?a:b;
}
inline bool equal(double a, double b) {
    return fabs(a - b) <= 1e-6;
}
inline bool isint(double a) {
    return equal(a, floor(a));
}
int get(double x, double y) {
    for(int i=1; i<=p; i++)
        if(equal(x, c[i][1]) && equal(y, c[i][2]))
            return i;
    p++;
    c[p][1] = x, c[p][2] = y;
    return p;
}
int main() {
    freopen("firez.in","r",stdin);
    freopen("firez.out","w",stdout);
    scanf("%d", &n);
    for(int i=0; i<=200; i++)
        for(int j=0; j<=200; j++)
            g[i][j] = 0x7fffffff;
    int x1, y1, x2, y2, t; double x3, y3, tt;
    for(int i=1; i<=n; i++) {
        scanf("%d %d %d %d %d", &x1, &y1, &x2, &y2, &t);
        x3 = (x1 + x2) / 2.0; y3 = (y1 + y2) / 2.0; tt = t / 2.0;
        p1 = get(x1, y1);
        p2 = get(x2, y2);
        p3 = get(x3, y3);
        g[p1][p3] = g[p3][p1] = g[p2][p3] = g[p3][p2] = tt;
        l[2*i-1][1] = x1; l[2*i-1][2] = y1;
        l[2*i-1][3] = x3; l[2*i-1][4] = y3;
        l[2*i][1] = x3; l[2*i][2] = y3;
        l[2*i][3] = x2; l[2*i][4] = y2 ;
        l[2*i-1][5] = tt; l[2*i][5] = tt;
    }
    for(int i=1; i<=p; i++)
        g[i][i] = 0;
    for(int k=1; k<=p; k++)
        for(int i=1; i<=p; i++)
            for(int j=1; j<=p; j++)
                if(k != i && i != j && j != k)
                    if(g[i][j] > g[i][k] + g[k][j])
                        g[i][j] = g[i][k] + g[k][j];
    s = 0x7fffffff;
    for(int i=1; i<=p; i++)
        if(isint(c[i][1]) && isint(c[i][2])) {
            m = 0;
            for(int j=1; j<=2*n; j++) {
                p1 = get(l[j][1], l[j][2]);
                p2 = get(l[j][3], l[j][4]);
                v = max(g[i][p1], g[i][p2]);
                u = fabs(g[i][p1] - g[i][p2]);
                if(equal(u, l[j][5]) && v > m)
                    m = v;
                if(u < l[j][5] && v + fabs(l[j][5] - u) / 2.0 > m)
                    m = v + fabs(l[j][5] - u) / 2.0;
            }
            if(m < s) s = m;
        }
    printf("%.4lf\n", s);
    return 0;
}