AOJ 0129 Hide-and-Seek Supporting System

二人の座標を(a,b),(c,d)とする。(ただしa<=c)
すべての円について、二人を結んだ線分と交点があるか判定する。
i)a=cの時
適切に処理してあげる。
ii)else
円の中心を(p,q),半径をrとする。
二点を通る直線の方程式はy=(d-b)/(c-a)*x+(bc-ad)/(c-a);
傾きをm,y切片をnとおく。(x-p)^2+(y-q)^2=r^2とy=mx+nからyを消去して両辺に(c-a)^2をかけて
整理してあげると{(d-b)^2+(c-a)^2}x^2+2{(bc-ad)(d-b)-p(c-a)^2-(c-a)(d-b)q}x+p^2(c-a)^2+(bc-ad-qc+qa)^2-r^2=0になる。D<0の時は見えてない、D=0のときは解がa＜x＜cのとき見えてない、それ以外の時見えてる、D>0のとき2解がともにa＜x＜cなら見えてない、それ以外の時見えてる。
判別式の判定でepsとか使いたくないなぁと思ったので無理やり全部整数係数になるようにした

int n,m;
vector<P> vec;
vector<int> rad;
P s,t;
ll sq(ll x)
{
	return x*x;
}
bool in(int x,P a)
{
	return sq(a.fi-vec[x].fi)+sq(a.sec-vec[x].sec)<rad[x]*rad[x];
}
bool check()
{
	for(int i=0;i<n;i++)
	{
		bool in1,in2;
		in1=in(i,s);in2=in(i,t);
		if(in1!=in2)return false;
		if(in1&&in2)continue;
		ll a=s.fi,b=s.sec,c=t.fi,d=t.sec,p=vec[i].fi,q=vec[i].sec;
		if(a>c)
		{
			swap(a,c);swap(b,d);
		}
		if(a==c)
		{
			if(min(b,d)<=vec[i].sec&&vec[i].sec<=max(b,d)&&abs(vec[i].fi-a)<=rad[i])
			{
				return false;
			}
			else continue;
		}
		ll A=sq(d-b)+sq(c-a);
		ll B=(b*c-a*d)*(d-b)-p*sq(c-a)-(c-a)*(d-b)*q;
		ll C=p*p*sq(c-a)+sq(b*c-a*d-q*c+q*a)-sq(rad[i])*sq(c-a);
		if(B*B-A*C<0)continue;
		else if(B*B-A*C==0)
		{
			if(a<=(-B/A)&&(-B/A)<=c)return false;
			else continue;
		}
		else
		{
			double ans1=(-B+sqrt(B*B-A*C))/A;
			double ans2=(-B-sqrt(B*B-A*C))/A;
			if(ans1>=a&&ans2<=c)return false;
			else continue;
		}
	}
	return true;
}
int main()
{
	while(1)
	{
		vec.clear();
		rad.clear();
		scanf("%d",&n);
		if(n==0)break;
		for(int i=0;i<n;i++)
		{
			P k;
			int r;
			scanf("%d %d %d",&k.fi,&k.sec,&r);
			vec.pb(k);
			rad.pb(r);
		}
		scanf("%d",&m);
		for(int i=0;i<m;i++)
		{
			scanf("%d %d %d %d",&t.fi,&t.sec,&s.fi,&s.sec);
			if(check())puts("Danger");
			else puts("Safe");
		}
	}
	return 0;
}