Curling Kickstart Problem

Kick Start - Google's Coding Competitions

Task:- Given the Radius of the house(Rh), Radius of stones(Rs), No of stones by team Red & Yellow( N & M), and the coordinates of each stone, Determine the team who won the game & also determine points by which team won.

Image from sample test case of problem

See the sample test case in the problem for a better understanding.

Approach:- Few observations can be made regarding the problem:

• No two stones overlap ( Given ).
• Stones tangent to the house can be considered valid ( Given ).
• No two stones are at precisely equal distance from the center of the house (at the origin ).
• The losing team always has 0 points, and the winning team always has X points where X>0. Hence the answer would always be “0 X” or “X 0”.

We can create a function get_distance(x,y) to get the distance of any stone at the x,y coordinate from the origin. This is because we would often need to determine the distance of stones from the center.

Also, for a stone to be considered for scoring, it should be either inside the radius of the house or at least tangent to it. In other words, stones which do not even intersect with the house are invalid.

We should sort the stones by each player in ascending order of their distances from the center to evaluate the results.

Suppose red & yellow are two lists/arrays of coordinates, if they are sorted we can directly determine the winner by comparing the distance of the first stones from each player.

IF ( get_distance( red[0] ) < get_distance( yellow[0] ) )

THEN RED team wins

ELSE YELLOW team wins

Now the remaining part is to calculate the score by which a team won. For that, we can consider the first(i.e — nearest to origin) stone by the losing team & we keep comparing the distance of this stone with each stone of the winning team. We can keep a counter to store how many stones the winning team has a distance less than the nearest stone of the losing team.

Code:-