움직이는 껍질의 정점
다이아몬드 II의견: 0
평면 위에 점들을 하나씩 추가하면서, 추가된 점들에 대한 질의를 처리하는 문제이다. 처음에는 점이 하나도 없다. 다음 두 종류의 연산을 입력 순서대로 총 \(M\)번 처리한다.
-
1 x y: 좌표가 \((x, y)\)인 점을 집합에 추가한다. -
2 a b: 지금까지 추가된 모든 점 \((x_i, y_i)\) 중 \(a \cdot x_i + b \cdot y_i\) 의 최댓값을 출력한다.
즉, 점이 계속 추가되는 도중에 임의의 방향 벡터 \((a, b)\)에 대한 점들의 사영(내적) 최댓값을 즉시 답해야 한다. 2 연산이 주어지는 시점에는 항상 최소 한 개의 점이 존재함이 보장된다.
\(1 \le M \le 100{,}000\)
\(-10^8 \le x, y \le 10^8\)
\(-10^8 \le a, b \le 10^8\), 단 \((a, b) \ne (0, 0)\)
2 연산은 점이 최소 하나 추가된 뒤에만 주어진다.
첫 줄에 연산의 개수 \(M\)이 주어진다.
이어서 \(M\)개의 줄에 위 형식의 연산이 한 줄에 하나씩 주어진다.
각 2 연산마다 \(a \cdot x_i + b \cdot y_i\) 의 최댓값을 한 줄에 하나씩 출력한다.
7
1 0 0
1 4 0
1 2 3
2 1 1
2 -1 0
1 5 -2
2 1 -1
5
0
7점 (0,0),(4,0),(2,3) 추가 후 (a,b)=(1,1): 각 점의 x+y는 0,4,5 -> 최대 5. (a,b)=(-1,0): -x의 최대는 (0,0)에서 0. 점 (5,-2) 추가 후 (a,b)=(1,-1): x-y는 0,4,-1,7 -> 최대 7 ((5,-2)).
5
1 -3 -3
2 0 1
1 1 5
2 0 1
2 1 0
-3
5
1(-3,-3) 추가 후 (0,1): y의 최대 -3. (1,5) 추가 후 (0,1): y의 최대 5. (1,0): x의 최대 1 ((1,5)).
riseoj 작성
출처 Original
평가 및 의견
움직이는 껍질의 정점
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
움직이는 껍질의 정점