Google Kickstart Round G 2022: Curling

In this post, we’ll discuss the solution to the Curling problem of Google Kickstart Round G 202. It’s a mathematical problem and revolves around one of the most simple but very useful formula. Ready to find out? Then, let’s go!

Problem

2022 is a year of the Winter Olympics! Curling has been one of the most popular winter sports as it requires skill, strategy, and sometimes a bit of luck.

In a curling game, two teams compete by sliding heavy granite stones on a long ice sheet. We call the teams the red team and the yellow team, as their stones are usually distinguished by the red and the yellow handle color. A curling game consists of several ends (subgames); in every end, the teams, each owning 8 stones, take turns to slide them across the long ice sheet toward a circular target area called the house. A stone may hit existing stones to change its own moving direction and other stones’ position (including knocking them out of play). Roughly speaking, the goal for a team is to make their stones as close to the center of the house as possible.

Geometrically, a house and a stone can be modeled as a circle and a disk (the region bounded by a circle), respectively, and the scoring rules at the conclusion of each end are formally summarized as follows.

• Each stone can be viewed as a disk of radius Rs on a 2-dimensional plane.
• The house is a circle of radius Rh centered at (0,0).
• Only stones in the house are considered in the scoring. A stone is in the house if any portion of the stone lies on or within the circle representing the house. Tangency also counts.
• A team is awarded 1 point for each of their own stones in the house such that no opponent’s stone is closer (in Euclidean distance) to the center than it. We assume in this problem that no two stones are equally close to the center (0,0).

Two teams are playing and have just delivered all their stones. The red team has N stones remaining on the curling sheet, centered at (X1,Y1),(X2,Y2),…,(XN,YN), while the yellow team has M stones remaining, centered at (Z1,W1),(Z2,W2),…,(ZM,WM). Now you are asked to figure out the scores of both teams.

Input

The first line of the input gives the number of test cases, T. T test cases follow.

Each test case begins with a line containing the two space-separated integers Rs and Rh.

The next line contains the integer N. Then N lines follow, the i-th line of which containing the two space-separated integers Xi and Yi.

After that, similarly, the next line contains the integer M. In the next M lines, the i-th line contains the two space-separated integers Zi and Wi.

Output

For each test case, output one line containing Case #x: y z, where x is the test case number (starting from 1), y is the score of the red team, and z is the score of the yellow team.

Limits

Time limit: 20 seconds.
Memory limit: 1 GB.
1≤T≤100.
1≤Rs<Rh≤10⁴.
0≤N≤8.
−2×10⁴≤Xi≤2×10⁴, for all i.
−2×10⁴≤Yi≤2×10⁴, for all i.
−2×10⁴≤Zi≤2×10⁴, for all i.
−2×10⁴≤Wi≤2×10⁴, for all i.
The distances between the center of each stone and the center of the house (0,0) are distinct, i.e., no two stones are equally close to the center of the house.
No two stones overlap (but two stones can be tangent).

Test Set 1

M=0.

Test Set 2

0≤M≤8.

Sample

Sample 1 –

Sample Input	Sample Output
2 1 5 4 1 -1 6 1 0 6 -5 0 0 10 100 2 -3 -4 200 200 0	Case #1: 3 0 Case #2: 1 0

Sample 2-

Sample Input	Sample Output
2 1 5 2 1 0 -3 0 1 0 2 10 50 2 -40 -31 -35 70 3 59 0 -10 0 30 40	Case #1: 1 0 Case #2: 0 2

Solution:

Solving a problem involving answering to a set of intuitive and relevant questions.

Pray tell me, what are those ‘relevant‘ questions?

Okay, first most important question – How to know if the stone is in the circle? As stones otherwise won’t be considered in the score calculation.

Well, the answer is the Euclidean distance formula off course. Let’s see how, with the help of a diagram-

Let’s consider the radius of the house to be R_h and that of the stone to be R_s. Let C_h at co-ordinates (x_h, y_h) and C_s at co-ordinates (x_s, y_s) be the centers of the house and stone respectively. As we can see from the diagram above, the Euclidean distance between the centers of the house and the stone should less or equal to than R_h+R_s. This is the maximum allowable distance between the two circles if we want the stone to be inside or on the house.

Representing this mathematically would look like –

So second question would be – Say we have a list of valid stones of teams red and yellow, Which stones will contribute to the score?

Again we can use the Euclidean distance formula here. For a team to score a point, no opponent’s stone is closer to the center than its stone So this implies, its stone should be closer than the closest opponent’s stone with respect to the center. Once we have found out the minimum Euclidean distance between the stones of both the teams and the center, we can then iterate over the stones again and calculate the scores such that –

1. The stone is inside or on the house.
2. The distance between the stone and house is less than that of the opponent team’s closest stone.

As we will be calculating the distances and points for the teams, it’s better to use functions which can be reused to avoid redundancy. Have a look at the code below for the complete picture:-

Time Complexity: O(N+M), where N = number of stones of Red team and M = number of stones of Yellow team. This is because we are just iterating over the stones of both the teams in two passes.

Space Complexity: O(1), constant space used.