눈송이 탕후루 만들기

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

요약
원점에서 시작해 주어진 M개의 후보 끝점 중 하나로 이어지는 선분 위에 놓인 과일 점의 최대 개수를 구한다.
난이도

보통10점 중 5점

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

문제

숙명여자대학교에 입학한 새내기들은 귀여운 눈송이를 좋아해 눈송이 탕후루를 만들려고 한다.

눈송이 모양 과일들이 2차원 좌표상에 있고 꼬치를 (0,0)(0, 0)에서 꼬치의 끝점을 놓을 수 있는 위치 중 하나인 (e_x,e_y)(e\_x, e\_y)까지 놓아 끝점을 포함한 선분상에 있는 모든 과일들을 꽂으려고 한다. 이때 꼬치의 끝점 후보 MM개가 주어지면 눈송이 과일을 최대한 많이 꽂을 수 있는 위치에서 꽂을 수 있는 과일의 수를 구해보자.

입력

존재하는 과일의 수 NN과 꼬치의 끝점을 놓을 수 있는 위치의 수 MM이 정수로 주어진다. (1≤N≤300,0001 \leq N \leq 300\\,000; 1≤M≤300,0001 \leq M \leq 300\\,000)

다음 NN개의 줄에 과일의 위치 (f_x,f_y)(f\_x, f\_y)가 공백으로 구분되어 주어진다. (−109≤f_x,f_y≤109-10^9 \leq f\_x, f\_y \leq 10^9, f_xf\_x, f_yf\_y는 정수) 중복된 과일의 위치는 주어지지 않는다.

다음 MM개의 줄에 꼬치의 끝점을 놓을 수 있는 위치 (e_x,e_y)(e\_x, e\_y)가 공백으로 구분되어 주어진다. (−109≤e_x,e_y≤109-10^9 \leq e\_x, e\_y \leq 10^9, e_xe\_x, e_ye\_y는 정수) 중복된 꼬치의 끝점은 주어지지 않는다.

(f_x,f_y)(f\_x, f\_y) 또는 (e_x,e_y)(e\_x, e\_y) 가 (0,0)(0, 0) 인 경우는 존재하지 않으며 (f_x,f_y)(f\_x, f\_y)와 (e_x,e_y)(e\_x, e\_y)가 같은 경우는 존재할 수 있다.

출력

과일을 최대한 많이 꽂을 수 있을 때 꽂히는 과일의 수를 출력한다.

예제1

  1. 예제 1

    입력
    9 5
    -1 -1
    -1 0
    -1 1
    1 0
    1 1
    1 2
    2 2
    2 4
    3 3
    0 3
    1 1
    4 0
    4 4
    3 6
    
    예상 출력
    3