Ovelhas

Um fazendeiro tem um grande rebanho de ovelhas. No início de cada dia ele as leva para um grande campo aberto da região, onde vários fazendeiros também levam suas ovelhas. Normalmente, suas ovelhas ficam próximas umas das outras, mas dessa vez ele não está tão certo de quais ovelhas são dele. Ele tem certeza que NN ovelhas são dele e está em dúvida sobre outras QQ ovelhas. Cada ovelha é identificada unicamente pelas suas coordenadas (X, Y) no plano.

Está na hora de voltar e o fazendeiro precisa juntar suas ovelhas para voltar para casa. Para tentar minimizar as chances de pegar uma ovelha de outra pessoa, ele pediu que você considerasse que uma ovelha O é dele se e somente se:

  • existirem outras três ovelhas dele A, B, C tais que O está contida no triângulo que tem como vértices A, B, C, ou

  • existirem outras duas ovelhas dele A, B tais que O pertence ao segmento de reta que tem como vértices A e B.

Dadas essas condições, responda quantas das QQ ovelhas pertencem ao fazendeiro.

Entrada

A primeira linha contém inteiros NN e QQ, representando respectivamente o número de ovelhas do fazendeiro e o número de ovelhas que ele não sabe se são dele. As NN linhas seguintes contém cada uma dois inteiros X e Y , representando as coordenadas no plano de uma ovelha do fazendeiro. As QQ linhas seguintes contém cada uma dois inteiros X e Y, representando as coordenadas no plano de uma ovelha que você deve classificar.

Saída

O seu programa deve imprimir um único inteiro, representando quantas das QQ ovelhas foram classificadas como sendo do fazendeiro.

Restrições

  • 2N1052 \leq N \leq 10^5
  • 1Q1051 \leq Q \leq 10^5
  • 109X,Y109-10^9 \leq X, Y \leq 10^9
  • Todos os pares (X, Y) na entrada são distintos.

Informações sobre a pontuação

  • Em um conjunto de testes somando 35 pontos, N,Q3000N, Q \leq 3000.
  • Em um conjunto de testes somando 15 pontos, todas as NN ovelhas estão sobre uma mesma reta (isso não vale para as QQ ovelhas).
Exemplos de Entrada Exemplos de Saída
5 5
-3 -17
5 7
2 -2
10 22
7 13
-1 -11
0 -8
-6 -26
39 -6
49 83
2
5 5
5 -3
3 -3
-5 1
4 -2
1 5
-2 5
0 -5
5 -5
-2 2
-1 -4
1
10 10
-8 -5
-4 6
1 -7
-6 7
-9 -4
5 1
9 6
7 -3
-9 6
5 8
7 -8
4 4
5 6
9 3
-2 3
4 -1
4 7
-8 -4
9 -5
1 5
7
Traduzido por Luis Paulo