计算气球半径让其不相交(五)

2013-12-12 14:36:47 · 作者: · 浏览: 546

 

    void tarjan(int now){

    dfn[now] = low[now] = ++ dp ;

    st[top ++] = now ;

    inst[now] = 1 ;

    for (int i = head[now] ; ~i ; i = ed[i].next ){

    int e = ed[i].e ;

    if(!dfn[e]){

    tarjan(e) ;

    low[now] = min(low[now] , low[e]) ;

    }

    else if(inst[e]){

    low[now] = min(low[now] , dfn[e]) ;

    }

    }

    if(low[now] == dfn[now]){

    ca ++ ;

    int xx ;

    do{

    xx = st[-- top] ;

    belong[xx] = ca ;

    inst[xx] = 0 ;

    }while(xx != now) ;

    }

    }

    int doit(){

    for (int i = 0 ; i < n 《 1 ; i ++ )if(!dfn[i])tarjan(i) ;

    for (int i = 0 ; i < n ; i ++ )if(belong[LL(i)] == belong[RR(i)])return 0 ;

    return 1 ;

    }

    int main() {

    while(cin 》 n ){

    for (int i = 0 ; i < n ; i ++ ){

    cin 》 x[LL(i)] 》 y[LL(i)] ;

    cin 》 x[RR(i)] 》 y[RR(i)] ;

    }

    double l = 0 , r = 30000 ,mid ;

    while(r - l > 1e-4){

    mid = (l + r) / 2 ;

    build(mid) ;

    if(doit())l = mid ;

    else r = mid ;

    }

    printf("%.2f\n",mid / 2) ;

    }

    return 0 ;

    }