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 BR 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++;

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2
0 0 3 5
1 1
3 3
2 6
-4 0
1 1 2 6 10
8 9
7 7
0

Output

x
+
cmd
C > P
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";
		}
	}
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
2
0 0 3 5
1 1
3 3
2 6
-4 0
1 1 2 6 10
8 9
7 7
0

Output

x
+
cmd
C > P
C = P
Advertisements

Demonstration


Previous
#1914 Beecrowd Online Judge Solution 1914 Whose Turn Is It? Solution in C++, Java, Js and Python
Next
#1924 Beecrowd Online Judge Solution 1924 Vitória and Her Indecision Solution in C++, Java, Js and Python