Geometry Darts
Time limit1sMemory limit256 MB
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 . Each of the next lines describes one shape in one of these three formats:
C x y r: a circle with center and radiusR x1 y1 x2 y2: a rectangle whose opposite corners are and , with andT x1 y1 x2 y2 x3 y3: a triangle with corners , and
The next line has the number of games . Each game takes six lines, and each line has the and coordinate of one landing point. The first three lines are Bob's throws and the last three are Hannah's.
- Every rectangle has sides parallel to the and 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 and .
- Every landing point is at least 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.