만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

제비 통신

면접 대비

시간 제한2초메모리 제한1024 MB

요약
N개의 점과 M개의 허용 기울기가 주어졌을 때, 같은 기울기의 직선 위에 놓인 서로 다른 두 점의 순서쌍 개수를 구합니다.
난이도

보통10점 중 4점

유형
해시맵, 수학
정답자
아직 제출이 없습니다

문제

한양이는 본인이 키우는 MM마리의 제비 중 한 마리에게 편지를 묶어 세종이에게 날리고 싶어 한다.

하지만 한양이가 키우는 제비들은 자기주장이 강해서, 출발 지점인 한양이의 위치에서 각자 정해진 기울기를 가진 직선 위의 경로로만 이동한다.

이 직선 위에 세종이가 있어야 한양이의 편지를 받을 수 있으며, 그때 제비 통신이 가능해진다.

한양이와 세종이를 배치할 수 있는 NN개의 좌표가 주어진다.

제비 통신이 가능하도록 둘을 배치할 수 있는 모든 경우의 수를 구하자.

입력

첫 번째 줄에 NN과 MM이 공백으로 구분되어 주어진다. (2≤N≤500002 \le N \le 50000, 1≤M≤101 \le M \le 10)

두 번째 줄에 MM개의 기울기 K1,K2,…,KMK_1, K_2, \dots, K_M이 공백으로 구분되어 주어진다. 모든 KK는 서로 다른 값이다. (−10≤Ki≤10-10 \le K_i \le 10)

이후 NN개의 줄에 걸쳐 ii번 점의 xx 좌표와 yy 좌표가 공백으로 구분되어 주어진다. 모든 좌표는 서로 다르다. (−109≤xi,yi≤109-10^9 \le x_i, y_i \le 10^9)

모든 입력은 정수로 주어진다.

출력

제비 통신이 가능하도록 한양이와 세종이를 배치할 수 있는 모든 경우의 수를 출력한다.

단, 한양이와 세종이를 같은 좌표에 배치할 수는 없다.

힌트

수학에서 기울기는 직선이 기울어진 정도를 나타내는 수이다. 데카르트 좌표계에서 직선의 기울기는 다음과 같이 나타낼 수 있다.

직선의 기울기=y의 변화량x의 변화량\text{직선의 기울기} = \frac{y\text{의 변화량}}{x\text{의 변화량}}

예제1

  1. 예제 1

    입력
    5 2
    1 -1
    1 1
    2 2
    3 2
    3 3
    5 -1
    
    예상 출력
    8