AOJ0129

問題:Hide-and-Seek Supporting System
円と２点の間の線分の当たり判定。ただし２点が両方共円の中にある場合は無視する。

#include<iostream>
#include<vector>
#include<complex>
using namespace std;

int main()
{
  int n,m;
  while(cin >> n,n)
  {
    vector<complex<double> > wallp;
    vector<double> wallr;
    for(int i=0;i<n; ++i)
    {
      int x,y,r;
      cin >> x >> y >> r;
      wallp.push_back(complex<double>(x,y));
      wallr.push_back(double(r));
    }
    
    cin >> m;
    for(int k=0;k<m; ++k)
    {
      int x,y;
      cin >> x >> y;
      complex<double> t(x,y);
      cin >> x >> y;
      complex<double> o(x,y);

      bool safe = false;

      for(int i=0;i<n; ++i)
      {
        if( abs(wallp[i]-t) < wallr[i] &&
            abs(wallp[i]-o) < wallr[i] ) continue;

        complex<double> a = wallp[i]-t;
        complex<double> b = wallp[i]-o;
        complex<double> t = b-a;

        double mlen = min(abs(a),abs(b));
        double ub = 1;
        double lb = 0;
        while(ub-lb>=1e-10)
        {
          double ubl = abs(a + t*ub);
          double lbl = abs(a + t*lb);
          double k = (ub+lb)/2;
          double mbl = abs(a + t*k);
          mlen = min(mlen, mbl);
          if(ubl > lbl)
            ub = k;
          else
            lb = k;
        }

        if(mlen <= wallr[i])
        {
          safe = true;
        }
      }

      cout << (safe ? "Safe" : "Danger") << endl;
    }
  }
  return 0;
}