AOJ0129 Hide-and-Seek Supporting System

解法
１．先ず太郎と鬼を結ぶ線分と円の中心点との距離を求める。
線分のベクトルと線分の端点と円の中心を結ぶベクトルのなす角が鈍角なら、線分と円の中心点との距離は、鈍角になる線分の端点と円の中心点との２点間の距離に当たる。鈍角の判定は内積が負かどうか（つまりθをなす角としたときcosθ<0かどうか）を見るのが楽。
もし線分の端点を見てどちらも鋭角になるのなら、線分を直線とみなして、点と直線の距離を求めることで解決する。

２．線分と円の中心点との距離が円の半径以内にあるとき、他方が円の外にあれば壁に狭まれてSafeが確定する。そうでない場合は円の中に二人が入っている場合で Danger に成り得るので、今見ている円だけでは確定しない。

反省
よく考えたら解法を思いつけたのでよかった。一度解いて二度目に解き直したとき、distanceLP内でcrossの絶対値が抜けてたのにサンプル通ってしまってバグ取りに時間がかかった。サンプル自体は強いので、交差判定がライブラリ化されてるならサンプルが通れば普通はジャッジも通ると思う。

#include <bits/stdc++.h>
using namespace std;

typedef complex<double> P;
typedef pair<double, P> C;
vector<C> circles;
#define FST first
#define SND second
typedef pair<P, P> S;
#define EPS (1e-5)

double dot(P a, P b) {
  return a.real()*b.real()+a.imag()*b.imag();
}

double cross(P a, P b) {
  return a.real()*b.imag()-a.imag()*b.real();
}

double distanceLP(S s, P a) {
  // d = |y||sin(th)| = |x||y|sin(th)/|x| = |cross(x, y)|/|x|
  return abs(cross(s.SND-s.FST, a-s.FST)) / abs(s.SND-s.FST);
}

double distanceSP(S s, P a) {
  // 2ベクトルのなす角が鈍角なら端点と１点との距離を返す
  if (dot(s.SND-s.FST, a-s.FST) < EPS) return abs(a-s.FST);
  if (dot(s.FST-s.SND, a-s.SND) < EPS) return abs(a-s.SND);
  
  return distanceLP(s, a);
}

int main() {
  int N;
  while(cin >> N && N) {
    circles.clear();
    circles.resize(N);
    for(int i=0; i<N; i++) {
      int x, y, r;
      cin >> x >> y >> r;
      circles[i] = C(r, P(x, y));
    }
    int Q; cin >> Q;
    while(Q--) {
      int x, y;
      cin >> x >> y; P taro(x, y);
      cin >> x >> y; P ogre(x, y);
      for(int i=0; i<N; i++) {
        if(distanceSP(S(taro, ogre), circles[i].SND) < circles[i].FST + EPS) {
          if(  abs(circles[i].SND-taro) > circles[i].FST + EPS
	    || abs(circles[i].SND-ogre) > circles[i].FST + EPS) {
            cout << "Safe" << endl;
            goto EXIT;
          }
        }
      }
      
      cout << "Danger" << endl;
      
    EXIT:;
    }
  }
  
  return 0;
}