| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 647 | 158 | 115 | 26.559% |
숙명여자대학교에 입학한 새내기들은 귀여운 눈송이를 좋아해 눈송이 탕후루를 만들려고 한다.
눈송이 모양 과일들이 2차원 좌표상에 있고 꼬치를 $(0, 0)$에서 꼬치의 끝점을 놓을 수 있는 위치 중 하나인 $(e_x, e_y)$까지 놓아 끝점을 포함한 선분상에 있는 모든 과일들을 꽂으려고 한다. 이때 꼬치의 끝점 후보 $M$개가 주어지면 눈송이 과일을 최대한 많이 꽂을 수 있는 위치에서 꽂을 수 있는 과일의 수를 구해보자.
존재하는 과일의 수 $N$과 꼬치의 끝점을 놓을 수 있는 위치의 수 $M$이 정수로 주어진다. (1ドル \leq N \leq 300,000円$; 1ドル \leq M \leq 300,000円$)
다음 $N$개의 줄에 과일의 위치 $(f_x, f_y)$가 공백으로 구분되어 주어진다. ($-10^9 \leq f_x, f_y \leq 10^9,ドル $f_x,ドル $f_y$는 정수) 중복된 과일의 위치는 주어지지 않는다.
다음 $M$개의 줄에 꼬치의 끝점을 놓을 수 있는 위치 $(e_x, e_y)$가 공백으로 구분되어 주어진다. ($-10^9 \leq e_x, e_y \leq 10^9,ドル $e_x,ドル $e_y$는 정수) 중복된 꼬치의 끝점은 주어지지 않는다.
$(f_x, f_y)$ 또는 $(e_x, e_y)$ 가 $(0, 0)$ 인 경우는 존재하지 않으며 $(f_x, f_y)$와 $(e_x, e_y)$가 같은 경우는 존재할 수 있다.
과일을 최대한 많이 꽂을 수 있을 때 꽂히는 과일의 수를 출력한다.
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