문제
진흥이는 지금 강가에서 그물망을 던져서 물고기를 잡는 중이다.
물고기의 움직임을 유심히 관찰하던 진흥이는 어떻게 하면 한 번에 가장 많은 물고기를 잡을 수 있을지 고민하고 있다.
그물을 던지려는 강의 정보를 좌표로 나타내면 현재 보이는 물고기들을 점으로 보고 좌표로 표시할 수 있다. 물고기들은 현재 움직이는 속도를 유지하면서 그 방향으로 계속 이동한다고 하자. 서로 다른 물고기가 같은 점을 지나갈 때에도 적절하게 잘 비켜가기 때문에 부딪히는 일은 없다.
그물을 던지는 위치는 고정되어 있으므로 물고기가 그물의 영역에 가장 많이 들어와 있을 때 그물을 던져야 한다.
그물의 가장자리에 있는 물고기는 그물을 올리는 순간 빠져 나가므로 잡을 수가 없고 그물의 안쪽에 들어온 물고기만 잡을 수 있다.
물고기들의 좌표와 이동정보를 바탕으로 진흥이가 어느 순간 그물을 던져야 하는지 그리고 그 경우 잡힌 물고기의 수는 몇 마리인지 구하는 프로그램을 작성하라.
입력
첫 행에는 그물의 정보 sx, sy, ex, ey가 입력된다. (sx, sy)는 그물의 왼쪽 아래의 좌표이고 (ex, ey)는 오른쪽 위의 좌표이다. ( 0 ≤ sx < ex ≤ 100000, 0 ≤ sy < ey ≤ 100000)
다음 행에는 물고기의 수 N이 주어진다. (1 ≤ N ≤ 100,000)
다음 N 행에는 물고기들의 정보를 의미하는 정수 xi, yi, mxi, myi가 주어진다.
xi, yi는 물고기의 현재 좌표이고 mxi는 myi는 초당 x좌표와 y좌표의 이동거리를 의미한다. (-200,000 ≤ xi, yi≤ 200,000, -10 ≤ mxi, myi≤ 10)
출력
가장 많은 물고기를 잡기 위해 그물을 던져야 하는 시간(지금부터 몇 초 후)과 그 때 잡히는 물고기의 수를 공백으로 구분하여 출력한다.
가장 많은 물고기를 잡는 시간이 여러 개인 경우 가장 짧은 시간을 출력한다.
예제 #1
0 0 5 3
2
-1 1 1 -1
5 2 -1 -1
1 1
예제 #2
4 3 10 7
7
7 6 -2 -1
9 10 -1 -2
10 10 -2 -3
10 8 -1 -1
11 8 -1 -1
11 7 -1 -1
8 6 1 -1
2 5
로그인해야 코드를 작성할 수 있어요.