BOJ 14059. Biathlon / BOJ 12997. 철인 2종 경기
문제 해석
BOJ 14059. Biathlon
철인 2종 경기에 \(N\)명의 선수가 참가한다. \(i\)번 선수의 달리기 속력과 수영 속력은 각각 \(r_i\)와 \(s_i\)로 일정하고, 선수들이 달릴 거리 \(R\)와 수영할 거리 \(S\)는 둘 다 음이 아닌 실수이다. 자신이 단독 우승을 할 수 있는 \((R, S)\) 순서쌍이 존재하는 선수들을 모두 찾아라.
BOJ 12997. 철인 2종 경기
위 문제와 같으나, \(R, S\)는 둘 다 양의 실수이고, 단독 우승뿐만 아니라 공동 우승도 포함한다.
접근
사실 BOJ 14059. 에서 \(R\)이나 \(S\)가 \(0\)인 경우는 고려하지 않아도 된다. 즉, BOJ 14059. 의 \(R, S\) 범위 조건은 BOJ 12997. 처럼 바꿔도 된다.
증명. 일반성을 잃지 않고 \(R=0\)이라고 가정하자. 만약 단독 우승자가 있다면 그 선수의 \(s_i\)는 유일하게 최대이므로 \(R\)이 \(0\)보다 크더라도 충분히 작으면 여전히 단독 우승이 가능하다. 따라서 \(R\)이나 \(S\)가 \(0\)이어야만 단독 우승이 가능한 선수는 있을 수 없다.
\(R\)과 \(S\)를 고정했을 때 \(i\)번 선수가 단독 우승한다는 것은 달리기와 수영 시간의 합이 다른 어떤 선수보다도 작다는 것이다:
\[\frac{R}{r_i} + \frac{S}{s_i} \lt \frac{R}{r_j} + \frac{S}{s_j} \quad \forall j \ne i. \quad \cdots (1)\]모든 \(i\)에 대하여 xy평면에 점 \(P_i := (\frac{1}{r_i}, \frac{1}{s_i})\)를 찍어보자. 두 변수 \(x, y\)에 관한 식
\[Rx + Sy = \frac{R}{r_i} + \frac{S}{s_i} \quad \cdots (2)\]는 \(P_i\)를 지나는 어떤 직선이 되고, \(R\)과 \(S\)가 모두 양수라서 이 직선의 기울기는 음수이다. 그러면 식 \((1)\)은 \(P_i\)를 제외한 모든 점들이 이 직선보다 위쪽에 있음을 의미한다. 즉, \(i\)번 선수가 어떤 \((R, S)\)에서 단독 우승을 할 수 있다는 것은 \(P_i\)를 지나는 어떤 직선의 기울기를 음수 범위에서 잘 조절해서 나머지 모든 점들보다 아래에 있게 할 수 있다는 것과 동치이다.
따라서 convex hull의 좌측 하단에 포함되고 다른 점과 좌표가 겹치지 않는 점들을 모두 골라주면 정답이 된다. 여기서 “convex hull의 좌측 하단”이란 convex hull을 따라 반시계 방향으로 돌 때 x좌표는 엄밀하게 증가하고 y좌표는 엄밀하게 감소하는 구간의 점들만 취한 것을 의미한다.
BOJ 12997. 은 단독 우승뿐만 아니라 공동 우승도 포함한다는 것만 달라진 문제이다. 똑같이 하되 BOJ 14059. 에서는 제외시켰던 좌표가 겹치는 경우와 세 점이 일직선에 있는 경우도 포함시키면 되고, binary search와 CCW를 통해 판별할 수 있다.