# Curling Solution Round G 2022 - Kick Start 2022

## Curling Solution (7pts, 10pts)

### 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 ${\mathbf{R}}_{\mathbf{s}}$ on a $2$-dimensional plane.
• The house is a circle of radius ${\mathbf{R}}_{\mathbf{h}}$ centered at $\left(0,0\right)$.
• 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 $\left(0,0\right)$.

Two teams are playing and have just delivered all their stones. The red team has $N$ stones remaining on the curling sheet, centered at $\left({\mathbf{X}}_{\mathbf{1}},{\mathbf{Y}}_{\mathbf{1}}\right),\left({\mathbf{X}}_{\mathbf{2}},{\mathbf{Y}}_{\mathbf{2}}\right),\dots ,\left({\mathbf{X}}_{\mathbf{N}},{\mathbf{Y}}_{\mathbf{N}}\right)$, while the yellow team has $M$ stones remaining, centered at $\left({\mathbf{Z}}_{\mathbf{1}},{\mathbf{W}}_{\mathbf{1}}\right),\left({\mathbf{Z}}_{\mathbf{2}},{\mathbf{W}}_{\mathbf{2}}\right),\dots ,\left({\mathbf{Z}}_{\mathbf{M}},{\mathbf{W}}_{\mathbf{M}}\right)$. 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 ${\mathbf{R}}_{\mathbf{s}}$ and ${\mathbf{R}}_{\mathbf{h}}$.

The next line contains the integer $N$. Then $N$ lines follow, the $i$-th line of which containing the two space-separated integers ${\mathbf{X}}_{\mathbf{i}}$ and ${\mathbf{Y}}_{\mathbf{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 ${\mathbf{Z}}_{\mathbf{i}}$ and ${\mathbf{W}}_{\mathbf{i}}$.

### Output

For each test case, output one line containing Case #x$x$: y$y$ z$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\le \mathbf{T}\le 100$.
$1\le {\mathbf{R}}_{\mathbf{s}}<{\mathbf{R}}_{\mathbf{h}}\le {10}^{4}$.
$0\le \mathbf{N}\le 8$.
$-2×{10}^{4}\le {\mathbf{X}}_{\mathbf{i}}\le 2×{10}^{4}$, for all $i$.
$-2×{10}^{4}\le {\mathbf{Y}}_{\mathbf{i}}\le 2×{10}^{4}$, for all $i$.
$-2×{10}^{4}\le {\mathbf{Z}}_{\mathbf{i}}\le 2×{10}^{4}$, for all $i$.
$-2×{10}^{4}\le {\mathbf{W}}_{\mathbf{i}}\le 2×{10}^{4}$, for all $i$.
The distances between the center of each stone and the center of the house $\left(0,0\right)$ 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

$\mathbf{M}=0$.

#### Test Set 2

$0\le \mathbf{M}\le 8$.

### Sample

Note: there are additional samples that are not run on submissions down below.
Sample Input
2
1 5
4
1 -1
6 1
0 6
-5 0
0
10 100
2
-3 -4
200 200
0

Sample Output
Case #1: 3 0
Case #2: 1 0


The following picture illustrates Sample Case #1. The big circle with a light blue interior represents the house, and the red disks represent the red team's stones. In this case, the yellow team has no stones left in the house, so the red team receives a point for each of their stone in the house. All the existing stones are in the house except the one centered at $\left(6,1\right)$ (it would have touched the house boundary if it were centered at $\left(6,0\right)$), so the red team gets $3$ points.

### Additional Sample - Test Set 2

The following additional sample fits the limits of Test Set 2. It will not be run against your submitted solutions.
Sample Input
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

Sample Output
Case #1: 1 0
Case #2: 0 2


The following picture illustrates Sample Case #1. Besides the big circle and the red disks, the yellow disk represents the yellow team's only remaining stone. In this case, both teams have stones inside the house. The red stone at $\left(1,0\right)$ is in the house and no yellow stone is closer than it to the center of the house, so it is worthy of a point. Although the other red stone (centered at $\left(-3,0\right)$) is also in the house, it is not worthy of a point because the yellow stone centered at $\left(0,2\right)$ is closer than it to the center $\left(0,0\right)$. The yellow stone is not worthy of a point, either, due to the existence of the red stone at $\left(1,0\right)$. Therefore, the red team gets $1$ point and the yellow team gets $0$ points.

## Solution:

We will find the distance of all the stones from the center and then will subtract the radius of the stone to check if it lies on or with the radius of the house and if it lies we add it to our red and yellow set respectively.
After this, we iterate in the red and the yellow set and check if the rival has any store closer to this or not using the upper bond and if the upper bound is the red.begin() or yellow.begin() means there is no closer stone of the opposite team and we increase our answer.

#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
int x = 1;
while (b)
{
if (b & 1) x *= a;
a *= a;
b >>= 1;
}
return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
const char* comma = strchr (names + 1, ',');
cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve(int tc) {
int ans;
int rs,rh,n,m;
cin>>rs>>rh>>n;
set<double>red,yellow;
int ans1=0,ans2=0;
int x,y;
for (int i = 0; i < n; i++)
{
cin>>x>>y;
double d=sqrt(x*x+y*y);
d-=rs;
if(d<=rh)red.insert(d);
}
cin>>m;
for (int i = 0; i < m; i++)
{
cin>>x>>y;
double d=sqrt(x*x+y*y);
d-=rs;
if(d<=rh)yellow.insert(d);
}

for(auto i:red){
if(yellow.empty())ans1++;
else{
auto it=yellow.upper_bound(i);
if(it==yellow.begin())ans1++;
}
}
for(auto i:yellow){
if(red.empty())ans2++;
else{
auto it=red.upper_bound(i);
if(it==red.begin())ans2++;
}
}
cout<<"Case #"<<tc<<""<<ans1<<" "<<ans2<<endl;

}

int32_t main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

clock_t z = clock();

int t = 1;
cin >> t;
int k=1;
while (t--) solve(k++);

return 0;
}

1. #include

using namespace std;

string caesarCipher(string s, int k) {
string ans="";
k%=26;
for(int i=0; i='a'&& c<='z'){
int j=c-'a';
j+=k;
j%=26;
char t='a'+j;
ans+=t;
}
else if(c>='A' && c<='Z'){
int j=c-'A';
j+=k;
j%=26;
char t='A'+j;
ans+=t;
}
else ans+=c;

}
return ans;
}

string decrypt(string s,int k){
string ans="";
k%=26;
for(int i=0; i='a'&& c<='z'){
int j=c-'a';
j-=k;
j%=26;
if(j<0)j+=26;
char t='a'+j;
ans+=t;
}
else if(c>='A' && c<='Z'){
int j=c-'A';
j-=k;
j%=26;
if(j<0)j+=26;
char t='A'+j;
ans+=t;
}
else ans+=c;

}
return ans;
}

int main()
{

string s;
getline(cin,s);
int k;
cin>>k;

string result = caesarCipher(s, k);

cout<<"Encrypted Text: "<<result<<endl;
cout<<"Decrypted Text: "<<decrypt(result,k)<<endl;
return 0;
}

2. #include
#include
#include

using namespace std;

string encrypt(string s, int k){
string str="";
k= k%26;
int end1= 'z'-k;
int end2= 'Z'-k;

for(int i=0;i='a')||(ch<=(char)end2 && ch>='A')){
str+= (char) ch+k;
}
else if((ch>=(char)end1 && ch<='z')||(ch>=(char)end2 && ch<='Z')){
str+= (char)((ch+ k)-26);
}
else{
str+=ch;
}
}

return str;
}

string decrypt(string s, int k){
string str="";
k= k%26;
int end1= 'a'+k;
int end2= 'A'+k;

for(int i=0;i=(char)end1 && ch<='z')||(ch>=(char)end2 && ch<='Z')){
str+= (char) ch - k;
}
else if((ch<=(char)end1 && ch>='a')||(ch<=(char)end2 && ch>='A')){
str+= (char)((ch- k)+26);
}
else str+=ch;
}
return str;
}
int main() {
string s;
cin>>s;
int k;
cin>>k;
cout<<"ENCRYPT"<<endl;
string ans= encrypt(s,k);
cout<<ans<<endl;
cout<<"DECRYPT"<<endl;
string code= decrypt(ans,k);
cout<<code<<endl;

}

3. #include
#include
#include

using namespace std;

int main() {
string s;
cin>>s;
unordered_mapmp;
for(auto c:s)mp[c]++;
for(auto it: mp){
cout<<it.first<<" occurs "<<it.second<<"times"<<endl;
}
return 0;
}

4. MAKE K = K+26 IF K<0

1. I don't know what are you talking about.

If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.