程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> ZOJ 3717 HDU 3622 二分+2-SAT

ZOJ 3717 HDU 3622 二分+2-SAT

編輯：C++入門知識

題意：給你N組氣球，每組有2個氣球，每組要取一個氣球，問最後使得N個氣球都不相交，則氣球半徑R最大是多少。

思路：直接二分半徑，然後2-sat判可行性。SCC之後如果有兩個同組的點在同一個強聯通分量裡，那麼則不可行。

這道題注意最後的二分結束之後還要取三位小數，看取了之後是否還是符合情況的，最後的那個操作是看別人的。。我WA到死了。。

我感覺這題這裡太坑了。。。

 #include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 2505  
#define inf 1<<28  
#define LL(x) ( x << 1 )  
#define RR(x) ( x << 1 | 1 )  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define PII pair<int,int>  
using namespace std; 
 
int t ; 
#define N 2005  
double x[N << 1] , y[N << 1] ,z[N << 1] ; 
 
struct kdq{ 
    int e , next ; 
}ed[N * 100] ; 
int head[N] , num ; 
int dfn[N << 1] , low[N << 1] ,st[N << 1] , top , dp ,inst[N << 1] , ca ,belong[N << 1] ; 
void add(int s ,int e){ 
    ed[num].e = e ; 
    ed[num].next = head[s] ; 
    head[s] = num ++ ; 
} 
void init(){ 
    mem(head , -1) ; 
    num = 0 ; 
    mem(dfn ,0) ; 
    mem(low, 0) ; 
    mem(st ,0) ; 
    mem(inst ,0) ; 
    mem(belong ,0) ; 
    top = dp = ca = 0 ; 
} 
inline double getdis(int i ,int j){ 
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j])) ; 
} 
 
void tarjan(int now){ 
    low[now] = dfn[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) ; 
    } 
} 
void build(double mid){ 
    init() ; 
    for (int i = 0 ; i < t ; i ++ ){ 
        for (int j = i + 1 ; j  < t ; j ++ ){ 
            if(getdis(LL(i),LL(j)) < mid){ 
                add(LL(i) , LL(j) ^ 1) ; 
                add(LL(j) , LL(i) ^ 1) ; 
            } 
            if(getdis(LL(i) ,RR(j)) < mid){ 
                add(LL(i) , RR(j) ^ 1) ; 
                add(RR(j) , LL(i) ^ 1) ; 
            } 
            if(getdis(RR(i) , LL(j)) < mid){ 
                add(RR(i) , LL(j) ^ 1) ; 
                add(LL(j) , RR(i) ^ 1) ; 
            } 
            if(getdis(RR(i) , RR(j)) < mid){ 
                add(RR(i) , RR(j) ^ 1) ; 
                add(RR(j) , RR(i) ^ 1) ; 
            } 
        } 
    } 
} 
 
int fuckit(){ 
    for (int i = 0 ; i  < t << 1 ; i ++ ){ 
        top = dp = 0 ; 
        if(!dfn[i])tarjan(i) ; 
    } 
    for (int i = 0 ; i < t ; i ++ ){ 
        if(belong[LL(i)] == belong[RR(i)])return 0 ; 
    } 
    return 1 ; 
} 
int main() { 
 
    while(cin >> t){ 
        for (int i = 0 ; i < t ;i ++ ){ 
            cin >> x[LL(i)] >> y[LL(i)] >> z[LL(i)] ; 
            cin >> x[RR(i)] >> y[RR(i)] >> z[RR(i)] ; 
        } 
//        cout << getdis(0 ,1) << endl;  
        double l = 0 , r = 20000 ; 
        double mid ; 
        while(r - l > 1e-5){ 
            mid = (l + r) / 2 ; 
            build(mid) ; 
            if(fuckit()){ 
                l = mid ; 
            } 
            else r = mid ; 
        } 
        double ans = mid / 2 ;//直接輸出 mid / 2 就WA到死。  
        char aa[222] ;//太惡心。  
        sprintf(aa ,"%.3f" , ans) ; 
        sscanf(aa , "%lf" ,&ans) ; 
        build(ans * 2 ) ; 
        if(!fuckit())ans -= 0.001 ; 
        printf("%.3f\n",ans) ; 
    } 
    return 0 ; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;

int t ;
#define N 2005
double x[N << 1] , y[N << 1] ,z[N << 1] ;

struct kdq{
    int e , next ;
}ed[N * 100] ;
int head[N] , num ;
int dfn[N << 1] , low[N << 1] ,st[N << 1] , top , dp ,inst[N << 1] , ca ,belong[N << 1] ;
void add(int s ,int e){
    ed[num].e = e ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;
}
void init(){
    mem(head , -1) ;
    num = 0 ;
    mem(dfn ,0) ;
    mem(low, 0) ;
    mem(st ,0) ;
    mem(inst ,0) ;
    mem(belong ,0) ;
    top = dp = ca = 0 ;
}
inline double getdis(int i ,int j){
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]) + (z[i] - z[j]) * (z[i] - z[j])) ;
}

void tarjan(int now){
    low[now] = dfn[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) ;
    }
}
void build(double mid){
    init() ;
    for (int i = 0 ; i < t ; i ++ ){
        for (int j = i + 1 ; j  < t ; j ++ ){
            if(getdis(LL(i),LL(j)) < mid){
                add(LL(i) , LL(j) ^ 1) ;
                add(LL(j) , LL(i) ^ 1) ;
            }
            if(getdis(LL(i) ,RR(j)) < mid){
                add(LL(i) , RR(j) ^ 1) ;
                add(RR(j) , LL(i) ^ 1) ;
            }
            if(getdis(RR(i) , LL(j)) < mid){
                add(RR(i) , LL(j) ^ 1) ;
                add(LL(j) , RR(i) ^ 1) ;
            }
            if(getdis(RR(i) , RR(j)) < mid){
                add(RR(i) , RR(j) ^ 1) ;
                add(RR(j) , RR(i) ^ 1) ;
            }
        }
    }
}

int fuckit(){
    for (int i = 0 ; i  < t << 1 ; i ++ ){
        top = dp = 0 ;
        if(!dfn[i])tarjan(i) ;
    }
    for (int i = 0 ; i < t ; i ++ ){
        if(belong[LL(i)] == belong[RR(i)])return 0 ;
    }
    return 1 ;
}
int main() {

    while(cin >> t){
        for (int i = 0 ; i < t ;i ++ ){
            cin >> x[LL(i)] >> y[LL(i)] >> z[LL(i)] ;
            cin >> x[RR(i)] >> y[RR(i)] >> z[RR(i)] ;
        }
//        cout << getdis(0 ,1) << endl;
        double l = 0 , r = 20000 ;
        double mid ;
        while(r - l > 1e-5){
            mid = (l + r) / 2 ;
            build(mid) ;
            if(fuckit()){
                l = mid ;
            }
            else r = mid ;
        }
        double ans = mid / 2 ;//直接輸出 mid / 2 就WA到死。
        char aa[222] ;//太惡心。
        sprintf(aa ,"%.3f" , ans) ;
        sscanf(aa , "%lf" ,&ans) ;
        build(ans * 2 ) ;
        if(!fuckit())ans -= 0.001 ;
        printf("%.3f\n",ans) ;
    }
    return 0 ;
}

HDU 3622

兩道題其實完全是一樣的，不過一題是3D，一題是2D，解法完全相同，不過這題二分之後不需要判可行性了。

#include <iostream>  
#include <cstdio>  
#include <algorithm>  
#include <string>  
#include <cmath>  
#include <cstring>  
#include <queue>  
#include <set>  
#include <vector>  
#include <stack>  
#include <map>  
#include <iomanip>  
#define PI acos(-1.0)  
#define Max 2505  
#define inf 1<<28  
#define LL(x) ( x << 1 )  
#define RR(x) ( x << 1 | 1 )  
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )  
#define ll long long  
#define mem(a,b) memset(a,b,sizeof(a))  
#define mp(a,b) make_pair(a,b)  
#define PII pair<int,int>  
using namespace std; 
 
#define N 105  
double x[N << 1] , y[N << 1] ; 
struct kdq{ 
    int e , next ; 
}ed[N * 1000] ; 
int dfn[N << 1] ,low[N << 1] , belong[N << 1] ,st[N << 1] ,inst[N << 1] ,head[N << 1] ; 
int dp , top , ca , num , n ; 
inline double getdis(int i ,int j){ 
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) ; 
} 
void add(int s ,int e){ 
    ed[num].e = e ; 
    ed[num].next = head[s] ; 
    head[s] = num ++ ; 
} 
void init(){ 
    mem(dfn ,0) ; 
    mem(low ,0) ; 
    mem(st ,0) ; 
    mem(head,-1) ; 
    mem(belong ,0) ; 
    mem(inst ,0) ; 
    dp = top = ca = num = 0 ; 
} 
void build(double mid){ 
    init() ; 
    for (int i = 0 ; i < n ; i ++ ){ 
        for (int j = i + 1 ; j < n ; j ++ ){ 
            if(getdis(LL(i) , LL(j)) < mid){ 
                add(LL(i) , LL(j) ^ 1) ; 
                add(LL(j) , LL(i) ^ 1) ; 
            } 
            if(getdis(LL(i) , RR(j)) < mid){ 
                add(LL(i) , RR(j) ^ 1) ; 
                add(RR(j) , LL(i) ^ 1) ; 
            } 
            if(getdis(RR(i) , LL(j)) < mid){ 
                add(RR(i) , LL(j) ^ 1) ; 
                add(LL(j) , RR(i) ^ 1) ; 
            } 
            if(getdis(RR(i) , RR(j)) < mid){ 
                add(RR(i) , RR(j) ^ 1) ; 
                add(RR(j) , RR(i) ^ 1) ; 
            } 
        } 
    } 
} 
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 ; 
} 

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <iomanip>
#define PI acos(-1.0)
#define Max 2505
#define inf 1<<28
#define LL(x) ( x << 1 )
#define RR(x) ( x << 1 | 1 )
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define PII pair<int,int>
using namespace std;

#define N 105
double x[N << 1] , y[N << 1] ;
struct kdq{
    int e , next ;
}ed[N * 1000] ;
int dfn[N << 1] ,low[N << 1] , belong[N << 1] ,st[N << 1] ,inst[N << 1] ,head[N << 1] ;
int dp , top , ca , num , n ;
inline double getdis(int i ,int j){
    return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j])) ;
}
void add(int s ,int e){
    ed[num].e = e ;
    ed[num].next = head[s] ;
    head[s] = num ++ ;
}
void init(){
    mem(dfn ,0) ;
    mem(low ,0) ;
    mem(st ,0) ;
    mem(head,-1) ;
    mem(belong ,0) ;
    mem(inst ,0) ;
    dp = top = ca = num = 0 ;
}
void build(double mid){
    init() ;
    for (int i = 0 ; i < n ; i ++ ){
        for (int j = i + 1 ; j < n ; j ++ ){
            if(getdis(LL(i) , LL(j)) < mid){
                add(LL(i) , LL(j) ^ 1) ;
                add(LL(j) , LL(i) ^ 1) ;
            }
            if(getdis(LL(i) , RR(j)) < mid){
                add(LL(i) , RR(j) ^ 1) ;
                add(RR(j) , LL(i) ^ 1) ;
            }
            if(getdis(RR(i) , LL(j)) < mid){
                add(RR(i) , LL(j) ^ 1) ;
                add(LL(j) , RR(i) ^ 1) ;
            }
            if(getdis(RR(i) , RR(j)) < mid){
                add(RR(i) , RR(j) ^ 1) ;
                add(RR(j) , RR(i) ^ 1) ;
            }
        }
    }
}
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 ;
}