제비 통신

면접 대비

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

요약
주어진 두 점을 이은 직선의 기울기가 주어진 M개의 기울기 중 하나와 같은 순서쌍의 개수를 센다.
난이도

보통10점 중 5점

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

문제

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

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

이 직선 상의 경로에 세종이가 있어야 한양이의 편지를 받으며 제비 통신이 가능해진다.

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

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

입력

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

두 번째 줄에 MM개의 기울기 K_1,K_2,…,K_MK\_1, K\_2, \dots, K\_M이 공백으로 구분되어 주어진다. 단, 주어지는 모든 KK는 중복된 값을 가지지 않는다. (−10≤K_i≤10)(-10 \le K\_i \le 10)

이후 NN개의 줄에 걸쳐 ii번 점의 xx 좌표와 yy 좌표가 공백으로 구분되어 주어진다. 단, 주어지는 모든 좌표는 중복된 값을 가지지 않는다. (−109≤x_i,y_i≤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