만드는 중입니다

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

눈송이 탕후루 만들기

면접 대비

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

요약
원점 (0, 0)에서 후보 끝점까지 꽂는 꼬치 하나가 꿸 수 있는 과일의 최대 개수를 구합니다.
난이도

보통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