XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: exploracao.x, onde x deve ser c, cpp, java, js ou py

Exploração do Capitão Levi

O Capitão Levi está indo para mais uma expedição pela tropa de exploração e, como sempre, ele resolveu olhar o mapa do local que ele e sua equipe estavam a caminho para que pudessem criar a melhor estratégia possível. Como todos sabem, a tropa de exploração é responsável por enfrentar titãs e deixar os habitantes da cidade mais protegidos.

O mapa do local pode ser resumido a um plano cartesiano e os titãs podem ser representados como pontos nesse plano. No entanto, seu dispositivo de manobra bidimensional(DMB) está defeituoso e agora Levi só consegue se locomover de um titã para outro titã durante o combate se eles estão em uma determinada direção, um em relação ao outro.

Se existe um titã no ponto A = (Xa, Ya) e um outro titã no ponto B = (Xb, Yb) ele consegue ir de A pra B se o coeficiente angular da reta que passa pelos pontos A e B for maior ou igual a P/Q. Observe que os pontos A e B devem ser distintos e que não existem pontos com a mesma coordenada X. Levi quer contar quantos pares de pontos distintos A e B existem, tais que há um titã em A e em B e ele consegue ir de A para B, ou seja (Ya - Yb)/(Xa - Xb) ≥ P/Q.

No entanto, existem muitos titãs no mapa e por isso Levi pediu sua ajuda para contabilizar os pares, lembrando que o par (A,B) e (B,A) são o mesmo par, ou seja, a ordem dos pontos não faz diferença.

Entrada

A primeira linha da entrada contém três números inteiros N, P e Q, indicando respectivamente a quantidade de titãs, e os dois inteiros descritos no enunciado. Cada uma das N linhas seguintes contém dois inteiros X e Y, indicando as coordenadas de um titã.

Saída

A saída consiste em um único número inteiro, representando a quantidade de pares de titãs entre os quais Levi pode se locomover respeitando as condições do enunciado.

Restrições

  • 2 ≤ N ≤ 5*105
  • -109 ≤ P, Q ≤ 109
  • P ≠ 0 e Q ≠ 0
  • 1 ≤ X, Y ≤ 107
  • Não existem dois titãs com a mesma coordenada X

Informações sobre a pontuação

  • Para um conjunto de casos de testes valendo 15 pontos, 2 ≤ N ≤ 103, P = 1 e Q = 1.
  • Para um conjunto de casos de testes valendo 20 pontos, 2 ≤ N ≤ 6*104, P = 1 e Q = 1.
  • Para um conjunto de casos de testes valendo 15 pontos, todos os titãs estão sobre uma mesma reta.
  • Para um conjunto de casos de testes valendo 20 pontos, P > 0 e Q > 0.
  • Para um conjunto de casos de testes valendo 30 pontos, não há restrições adicionais.

Exemplos

Entrada
6 1 1
1 1
4 6
2 5
8 2
7 1
6 10
Saída
6
	

 

Entrada
6 1 1
7 7
1 1
2 2
16 16
11 11
200 200
Saída
15
	

 

Entrada
8 418732 641936
60693 28595
15649 57089
77335 92158
57291 25242
21420 56599
62278 58106
52009 12362
41982 64916
Saída
11
	

 

Tarefas Programação Nível 2
Promoção:
sbc
Patrocínio
 
Apoio
 
Coordenação