Google Kick Start Round G - Curling Problem Solution | ATC Tech Adda

Google Kick Start 2022 Round G - Curling Problem Solution

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 (X₁,Y₁),(X₂,Y₂),…,(X_N,Y_N), while the yellow team has M stones remaining, centered at (Z₁,W₁),(Z₂,W₂),…,(Z_M,W_M). 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 R_s and R_h.
The next line contains the integer N. Then N lines follow, the i-th line of which containing the two space-separated integers X_i and Y_i.
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 Z_i and W_i.

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.

---

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define endl "\n"

ll dist(ll x, ll y) { return x * x + y * y; }
ll sqr(ll x) { return x * x; }

int main()
{
    int test;
    cin >> test;
    for (int t = 1; t <= test; t++)
    {
        ll Rs, Rh, N, M;
        cin >> Rs >> Rh;
        cin >> N;
        ll teamA[N][2];
        for (int i = 0; i < N; i++)
        {
            cin >> teamA[i][0] >> teamA[i][1];
        }
        cin >> M;
        ll teamB[M][2];
        for (int i = 0; i < M; i++)
        {
            cin >> teamB[i][0] >> teamB[i][1];
        }
        ll score_red = 0, score_yellow = 0;
        if (M == 0)
        {
            for (int i = 0; i < N; i++)
            {
                score_red += (sqr(teamA[i][0]) + sqr(teamA[i][1])) <= sqr((Rh + Rs));
            }
        } else
        {
            for(int i = 0; i < N; i++) {
                bool is_scoring = dist(teamA[i][0], teamA[i][1]) <= sqr((Rs + Rh)); // Inside house.
                for(int j = 0; j < M; j++) {
                    is_scoring &= dist(teamA[i][0], teamA[i][1]) < dist(teamB[j][0], teamB[j][1]);
                }
                score_red += is_scoring;
            }
            for(int i = 0; i < M; i++) {
                bool is_scoring = dist(teamB[i][0], teamB[i][1]) <= sqr((Rs + Rh)); // Inside house.
                for(int j = 0; j < N; j++) {
                    is_scoring &= dist(teamB[i][0], teamB[i][1]) < dist(teamA[j][0], teamA[j][1]);
                }
                score_yellow += is_scoring;
            }
        }
        cout << "Case #" << t << ": " << score_red << " " << score_yellow << endl;
    }
    return 0;
}
	

Happy Coding🙂.