문제
진흥이는 지금 강가에서 그물망을 던져서 물고기를 잡는 중이다.
물고기의 움직임을 유심히 관찰하던 진흥이는 T초 후에 그물을 어디에 던지면 한 번에 가장 많은 물고기를 잡을 수 있을지 고민하고 있다.
그물을 던지려는 강의 정보를 좌표로 나타내면 현재 보이는 물고기들을 점으로 보고 좌표로 표시할 수 있다. 물고기들은 현재 움직이는 속도를 유지하면서 그 방향으로 계속 이동한다고 하자. 서로 다른 물고기가 같은 점을 지나갈 때에도 적절하게 잘 비켜가기 때문에 부딪히는 일은 없다.
그물의 가장자리에 있는 물고기는 그물을 올리는 순간 빠져 나가므로 잡을 수가 없고 그물의 안쪽에 들어온 물고기만 잡을 수 있다.
물고기들의 현재 위치 좌표와 이동정보를 바탕으로 T초 후에 진흥이가 그물을 던질 때,
잡히는 물고기의 최대 마리수를 구하는 프로그램을 작성하시오.
입력
첫 행에는 그물의 크기 S와 초를 나타내는 T가 정수로 주어진다.
그물은 한 변의 길이가 S인 정사각형이며 진흥이는 축에 평행 형태로 그물을 던진다. (1 ≤ S ≤ 1,000) (1 ≤ T ≤ 100,000)
다음 행에는 물고기의 수 N이 정수로 주어진다. (1 ≤ N ≤ 100,000)
다음 N 행에는 물고기들의 정보를 의미하는 정수 xi, yi, mxi, myi가 정수로 주어진다.
xi, yi는 물고기의 현재 좌표이고 mxi는 myi는 초당 x좌표와 y좌표의 이동거리를 의미한다. (-200000 ≤ xi, yi≤ 200000, -10 ≤ mxi, myi≤ 10)
출력
T초 후에 진흥이가 그물을 던질 때 잡을 수 있는 물고기의 최대 마리수를 출력한다.
예제
3 2
2
-1 1 1 -1
5 2 -1 -1
2
출처
2018 ICT Award KOREA
로그인해야 코드를 작성할 수 있어요.