Under construction

Still being built. Things may change

Geometry Darts

Time limit1sMemory limit256 MB

Summary
Count how many circles, rectangles, and triangles contain each of six dart throws and name Bob, Hannah, or Tied as the winner of each game.
Level

Easy3 of 10

Topics
Geometry, Brute force
Solved
No attempts yet

Problem

Bob and Hannah like darts but are not good at it, so finishing a round of 501 takes them forever. They put the dartboard away, taped geometric shapes to the wall instead, and now score a dart by how many shapes it goes through. To keep the scoring simple they use only circles, triangles and rectangles.

In one game each player throws three darts. A dart scores the number of shapes that contain the point it landed on, and a player's score is the sum over their three darts. Given the shapes and the throws, report the winner of each game.

Input

The first line has the number of shapes SS. Each of the next SS lines describes one shape in one of these three formats:

  • C x y r: a circle with center (x,y)(x, y) and radius rr
  • R x1 y1 x2 y2: a rectangle whose opposite corners are (x1,y1)(x_1, y_1) and (x2,y2)(x_2, y_2), with x1<x2x_1 < x_2 and y1<y2y_1 < y_2
  • T x1 y1 x2 y2 x3 y3: a triangle with corners (x1,y1)(x_1, y_1), (x2,y2)(x_2, y_2) and (x3,y3)(x_3, y_3)

The next line has the number of games NN. Each game takes six lines, and each line has the xx and yy coordinate of one landing point. The first three lines are Bob's throws and the last three are Hannah's.

  • 0<S≤10000 < S \le 1000
  • 0<N≤10000 < N \le 1000
  • Every rectangle has sides parallel to the xx and yy axes.
  • The three corners of a triangle are never collinear.
  • All coordinates are real numbers given with up to 6 digits after the decimal point.
  • Every shape fits inside the rectangle with opposite corners (−1000,−1000)(-1000, -1000) and (1000,1000)(1000, 1000).
  • Every landing point is at least 10−610^{-6} away from the boundary of every shape.

Output

Print the winner of each game on its own line. Print Bob if Bob scores higher, Hannah if Hannah scores higher, and Tied if the two scores are equal.

Examples3

  1. Example 1

    Input
    3
    C 0.0 0.0 5.0
    R -1.0 -1.0 7.0 7.0
    T 0.0 0.0 -3.0 0.0 0.0 -8.0
    1
    0.0 4.1
    0.0 6.2
    0.0 8.1
    -0.5 -0.5
    -0.5 -2.0
    -0.5 -5.1
    
    Expected output
    Hannah
    
  2. Example 2

    Input
    3
    C 0.0 0.0 10.0
    R 0.0 0.0 5.0 5.0
    T 0.0 0.0 10.0 0.0 0.0 10.0
    1
    1.0 1.0
    2.0 2.0
    3.0 1.0
    9.0 9.0
    -20.0 0.0
    0.5 -0.5
    
    Expected output
    Bob
    
  3. Example 3

    Input
    2
    C 0.0 0.0 4.0
    R -2.0 -2.0 2.0 2.0
    2
    1.0 1.0
    -1.0 -1.0
    3.0 0.0
    -1.0 1.0
    1.0 -1.0
    0.0 3.0
    100.0 100.0
    -100.0 -100.0
    50.0 -50.0
    200.0 0.0
    0.0 -200.0
    -300.0 400.0
    
    Expected output
    Tied
    Tied