Algorithm


Problem Name: 2 AD-HOC - beecrowd | 2343

Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2343

Caçadores de Mitos

 

Por OBI - Olimpíada Brasileira de Informática 2009 BR Brazil

Timelimit: 1

Jorge é um apresentador de televisão que comanda a versão brasileira do grande sucesso Caçadores de Mitos, onde se estuda um mito para descobrir se é fato ou apenas um boato.

No próximo episódio, Jorge deverá apresentar o mito que diz que ”os raios não caem duas vezes no mesmo lugar”, referindo-se aos raios das tempestades de chuva.

Para isso, foi até a cidade de Eletrolândia, que é a cidade com maior ocorrência de raios no mundo. O prefeito tem tanto orgulho desse título que mandou criar um sistema para registrar os raios. Jorge conseguiu um relatório com as ocorrências de cada raio que caiu na cidade nos últimos anos.

O mapa de Eletrolândia é um retângulo. Para o sistema de registro a cidade é subdividida em quadrados de um metro de lado, denominados quadrantes. Assim, se a cidade tem 300 metros de largura e 1000 de comprimento, ela será subdividida em 300.000 quadrantes. O sistema de registro armazena o quadrante em que o raio caiu. Cada quadrante é identificado pelas suas coordenadas X e Y, conforme ilustra a figura abaixo, que exemplifica um mapa de uma cidade com oito metros de comprimento por cinco metros de largura (quarenta quadrantes).

Como os quadrantes são relativamente pequenos, Jorge decidiu que se dois raios caíram no mesmo quadrante, pode-se considerar que caíram no mesmo lugar.

Sua missão é escrever um programa que receba as coordenadas dos raios que caíram em Eletrolândia nos últimos anos e determine se o mito estudado é realmente apenas um mito ou pode ser considerado verdade.

 

Entrada

 

A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado).

A primeira linha da entrada contém um número inteiro N (2 ≤ N ≤ 500.000) representando o número de registros de raios no relatório. Cada uma das N linhas seguintes contém 2 números inteiros X, Y (0 ≤ X, Y ≤ 500), representando o registro de um raio que caiu no quadrante cujas coordenadas são (X, Y).

 

Saída

 

Seu programa deve imprimir, na saída padrão, o número 0 se nenhum raio caiu no mesmo lugar, ou o número 1 caso contrário. Note que você deve imprimir o número 1 mesmo que haja mais do que 1 par de raios que caíram no mesmo lugar.

 

 

 

Exemplos de Entrada Exemplos de Saída

5

1 1

2 3

3 3

4 2

4 4

0

 

 

 

8

1 1

2 2

2 3

4 4

2 3

6 5

9 11

10 10

1

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>

#define true 1
#define false 0
#define MAXSIZE 600

unsigned short grid[MAXSIZE][MAXSIZE];

int main (void)
{

	unsigned n, x, y;
	_Bool flag = false;
	unsigned linha, coluna;

	scanf("%d", &n);

	while (n--)
	{

		scanf("%u %u", &x, &y);

		if (grid[x][y])
			flag = true;
		else
			grid[x][y] = 1;

	}

	printf("%c\n", flag ? '1' : '0');

}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5
1 1
2 3
3 3
4 2
4 4
Advertisements

Demonstration


Previous
#2342 Beecrowd Online Judge Solution 2342 Overflow Solution in C, C++, Java, Js and Python
Next
#2344 Beecrowd Online Judge Solution 2344 Notas da Prova Solution in C, C++, Java, Js and Python