Codeforces 27 D. Ring Road 2
問題
円周上にn個の点が順に並んでいる。
これらにm本の辺を、互いに交差しないように引きたい。
それが可能なら、それぞれの辺は円の内側に引かれるか、外側に引かれるかを
具体例に対して一通り出力し、
不可能なら、Impossibleと出力せよ。
制約条件
n,m≦100
方針
まず一本の辺を適当に内か外か決める。
そしたら、その一本が決まったことにより、内か外かが限定される辺が出てくるので、
それらを確定させる。
決まる辺がなくなったら、他の辺は、上の決め方より、今までの辺が内にあったか外にあったかと独立であったことがわかるので、
また一つの辺を適当に決めて、そこから決まる辺を確定させて……を繰り返せばよいことがわかる。
最後に辺に矛盾(交差)がないかを調べる。
ソースコード
int n,m; int l[100],r[100]; int io[100]; bool cross(int a,int b){ if(l[a]>r[a])swap(l[a],r[a]); if(l[b]>r[b])swap(l[b],r[b]); if(l[a]==l[b]||l[a]==r[b]||r[a]==l[b]||r[a]==r[b])return 0; return (l[a]<l[b]&&l[b]<r[a])^(l[a]<r[b]&&r[b]<r[a]); } bool solve(){ for(;;){ for(;;){ bool update=0; rep(i,m)rep(j,m)if(io[i]==0&&io[j]&&cross(i,j)){ io[i]=-io[j]; update=1; goto NEXT; } if(!update)break; NEXT:; } int p=-1; rep(i,m)if(io[i]==0)p=i; if(p<0)break; io[p]=1; } rep(i,m)rep(j,i)if(io[i]==io[j]&&cross(i,j))return 0; return 1; } void run() { cin>>n>>m; rep(i,m){ cin>>l[i]>>r[i]; l[i]--; r[i]--; } memset(io,0,sizeof(io)); if(solve())rep(i,m)cout<<(io[i]<0?"i":"o")<<(i==m-1?"\n":""); else cout<<"Impossible"<<endl; }