문제
2차원 평면에 직선이 N개 주어진다.
i번째 직선은 y = aix + bi로 주어진다.
이 때, 다음 쿼리를 처리하는 프로그램을 작성하자.
1 x: 모든 점들 중, aix + bi의 최댓값을 출력한다.
2 a b: 직선 y = ax + b를 하나 추가한다.
입력
첫 번째 줄에 점의 개수를 의미하는 자연수 N과 쿼리의 개수 Q가 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ Q ≤ 100,000)
두 번째 줄부터 N개의 줄에 점의 위치 (xi, yi)가 주어진다. (-109 ≤ ai, bi ≤ 109)
그 다음 줄부터 Q개의 줄에 각 쿼리의 번호 q와, 1번이라면 x가, 2번이라면 a b가 정수로 주어진다. (-109 ≤ x ≤ 109, -109 ≤ a, b ≤ 109)
출력
1번 쿼리에 대해, 모든 직선들 중, aix + bi의 최댓값을 출력한다.
예제
5 7
-2 2
-1 1
3 3
5 6
7 -5
1 -10
1 -2
2 4 8
1 0
1 2
2 8 0
1 10
22
6
8
16
80
로그인해야 코드를 작성할 수 있어요.