AOJ 0129 Hide-and-Seek Supporting System
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0129
PKUの調子がわるいようなのでAOJへ。
何度かWAを出してのAC。
最初は円と線分が交差しているかを判定してたのですが、それだとWAになって、原因が分からなかったので、円の中心から線分に伸ばした垂線の座標が円の中にあり、かつ、その座標が線分上にある時にsafeにしました。その他細かいところで弾いたりしてます。
式の整理は相変わらずwolframさんに活躍してもらいました。
int wx[100],wy[100],r[100]; main(){ int n; while(cin>>n,n){ rep(i,n)cin>>wx[i]>>wy[i]>>r[i]; int m; cin>>m; while(m--){ int a,b,c,d; cin>>a>>b>>c>>d; bool safe=false; rep(i,n){ if(a==c && b==d)break; int e=wx[i],f=wy[i],g=r[i]; bool myin=(e-a)*(e-a)+(b-f)*(b-f)<g*g; bool enin=(e-c)*(e-c)+(f-d)*(f-d)<g*g; if(myin!=enin){ safe=true; break; } if(myin && enin)continue; int varxy=(a*a-2*a*c+b*b-2*b*d+c*c+d*d); double xx=(a*a*e-a*b*d+a*b*f-2*a*c*e+a*d*d-a*d*f+b*b*c-b*c*d-b*c*f+c*c*e+c*d*f); xx=xx/varxy; double yy=(a*a*d-a*b*c+a*b*e-a*c*d-a*d*e+b*b*f+b*c*c-b*c*e-2*b*d*f+c*d*e+d*d*f); yy=yy/varxy; if((e-xx)*(e-xx)+(f-yy)*(f-yy)>g*g)continue; if((a<=xx && xx<=c) || (c<=xx && xx<=a)){ safe=true; break; } } if(safe)cout<<"Safe"<<endl; else cout<<"Danger"<<endl; } } }