Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1920
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1920
Fountain of Desires
By Dâmi Henrique, Inatel 
Brazil
Timelimit: 1
Tired of throwing coins into the fountain of desires and have no wish granted, Chiquinha and Popis decided to use the source as a target in coin throwing game. They will take a distance from the source and throw alternately N coins each trying to hit it. Each coin may fall inside(dentro) the fountain, on the edge(borda) or outside.
Given the coordinate (cx, cy) of the center of the fountain, the radius of which is considered inside (r1), and the radius of the edge (r2), your task is the check the throw of both girls and say who hit more coins into the fountain. In case of a tie, the winner is the one that hit more in the edge. If the tie persists, we consider that the game ended in a draw.
Note: If a coin fall exactly into any circle extremes, it shall be considered edge(red dots in the image below).
Input
There will be several test cases. The first line in each case initiates an integer N (1 ≤ N ≤ 1000) representing the number of coins that each girl launched. The second line contains four integers, CX, CY (-1000 ≤ CX, CY≤ 1000), R1 and R2
(1 ≤ R1 < R2 ≤ 5000), representing respectively the center of the fountain and the radius as shown in the figure above.
After that, 2*N lines follow, each one having two integers X and Y representing the x and y coordinate where a coin dropped. Remember that they play alternately and Chiquinha always plays first.
The input ends with C = 0, which should not be processed.
Output
For each case, output C > P in case Chiquinha wins the dispute, P > C case Popis win or C = P case the game ends tied.
| Input Sample | Output Sample |
|
2 0 0 3 5 1 1 3 3 2 6 -4 0 1 1 2 6 10 8 9 7 7 0 |
C > P C = P |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#define true 1
#define false 0
#define POW(a) a * a
#define C chiquinha.dentro
#define CC chiquinha.borda
#define P popis.dentro
#define PP popis.borda
#define T printf("TESTE\n")
typedef struct pontos{
int dentro;
int borda;
} pontos;
void count(int, int, int, pontos *);
int main (void)
{
int px, py, i;
int r1, r2, cx, cy;
unsigned short qtsMoedas;
while (scanf("%hu", &qtsMoedas), qtsMoedas)
{
scanf("%d %d %d %d", &cx, &cy, &r1, &r2);
r1 *= r1;
r2 *= r2;
pontos chiquinha = { 0 }, popis = { 0 };
for (i = 0; i < qtsMoedas; ++i)
{
scanf("%d %d", &px, &py);
count(POW((px - cx)) + POW((py - cy)), r1, r2, &chiquinha);
scanf("%d %d", &px, &py);
count(POW((px - cx)) + POW((py - cy)), r1, r2, &popis);
}
printf("%s\n", C > P ? "C > P" : C < P ? "P > C" : CC > PP ? "C > P" : PP > CC ? "P > C" : "C = P");
}
}
void count(int dist, int raio1, int raio2, pontos *tmp)
{
if (dist < raio1)
tmp->dentro++;
else if (dist >= raio1 && dist < = raio2)
tmp->borda++;
}
Input
0 0 3 5
1 1
3 3
2 6
-4 0
1 1 2 6 10
8 9
7 7
0
Output
C = P
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
int xc;
int yc;
int r1;
int r2;
int dist(int x, int y)
{
return (x - xc) * (x - xc) + (y - yc) * (y - yc);
}
int main()
{
int n;
int chiqx, chiqy;
int popx, popy;
int chiqdentro, chiqborda;
int popdentro, popborda;
ios_base :: sync_with_stdio(0); cin.tie(0);
while (cin >> n)
{
if (!n) return 0;
cin >> xc >> yc >> r1 >> r2;
r1 *= r1;
r2 *= r2;
chiqdentro = chiqborda = popdentro = popborda = 0;
for (int i = 0 ; i < n ; ++i)
{
cin >> chiqx >> chiqy >> popx >> popy;
int d1 = dist(chiqx, chiqy);
int d2 = dist(popx, popy);
if (d1 < r1) ++chiqdentro;
else if (r1 <= d1 && d1 <= r2) ++chiqborda;
if (d2 < r1) ++popdentro;
else if (r1 <= d2 && d2 <= r2) ++popborda;
}
if (chiqdentro != popdentro)
{
if (chiqdentro > popdentro) cout << "C > P\n";
else cout << "P > C\n";
}
else
{
if (chiqborda != popborda)
{
if (chiqborda > popborda) cout << "C > P\n";
else cout << "P > C\n";
}
else cout << "C = P\n";
}
}
}
Input
0 0 3 5
1 1
3 3
2 6
-4 0
1 1 2 6 10
8 9
7 7
0
Output
C = P