Triangle and Circle

Time Limit : 1 sec, Memory Limit : 65536 KB

三角形と円

平面上にある三角形と円の位置関係を判定するプログラムを作成してください。対象となる図形はいずれも境界を含むものとします。 三角形は 3 頂点の位置が与えられ、円は中心の位置と半径が与えられます。位置は直交座標系による2つの整数の組によって与えられます。半径も整数で与えられます。

Input

複数のデータセットの並びが入力として与えられます。入力の終わりはゼロふたつの行で示されます。 各データセットは以下の形式で与えられます。

x1 y1
x2 y2
x3 y3
xc yc
r

1行目から3行目に、三角形の第 i の頂点座標 xi, yi が与えられます。4行目に円の中心の座標 xc, yc、5行目に円の半径 r が与えられます。与えられる入力はすべて、1 以上 10,000 以下の整数とします。

データセットの数は 100 を超えません。

Output

入力データセットごとに以下の形式で判定結果を1行に出力します。

円が三角形に含まれる場合 a
三角形が円に含まれる場合 b
それ以外の場合で、共通部分がある場合には c
共通部分がない場合には d

Sample Input

1 1
3 1
3 3
3 2
3
3 12
9 3
11 12
8 7
5
15 3
17 7
22 5
7 6
4
6 11
8 2
16 9
10 8
2
0 0

Output for the Sample Input

b
c
d
a

Source: PC Koshien 2007, Preliminary Round , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2007
http://www.pref.fukushima.jp/pc-concours/