BOJ 14059 Biathlon
BOJ 14059 Biathlon
문제 내용
명의 선수가 달리기와 수영으로 이루어진 철인 2종 경기에 참가합니다. 번째 선수의 달리기 속도는 , 수영 속도는 입니다. 달리기 거리 과 수영 거리 를 원하는 양의 실수로 정할 수 있을 때, 우승 가능성이 있는 선수를 모두 구하세요. 여러 선수가 동시에 결승점에 도착할 경우 아무도 우승으로 인정되지 않습니다.
입력
첫 줄에는 이 주어집니다.
다음 줄에는 각 선수에 대한 와 가 주어집니다. 이 값들은 정수입니다. 범위는 서브태스크를 참고하세요.
출력
우승 가능성이 있는 모든 선수의 인덱스를 오름차순으로 한 줄에 출력합니다. 첫 번째 선수의 인덱스는 0입니다. 우승 가능성이 있는 선수가 없다면 -1을 대신 출력합니다.
문제 풀이
스포일러
번째 선수가 결승점에 도착하는 데 걸리는 시간은 이며, 이 값이 가장 작은 선수가 우승합니다.
이는 2차원 평면에 의 점의 집합이 있을 때 그 중에서 가 최소인 점을 구하는 것과 같으며, 이는 점들의 볼록 껍질에 기울기 인 직선이 아래쪽에서 접할 때 그 접점을 구하는 것과 같습니다.
기울기는 원하는 음의 실수로 설정할 수 있으므로, 볼록 껍질의 아래쪽 구간에 해당하는 모든 점의 인덱스를 출력하면 됩니다. lower hull의 양끝에서 조건에 맞지 않는 점들을 제거해야 하는 점에 주의합니다.
중복 점 처리는 각 좌표를 그 좌표에 있는 선수들의 목록으로 대응시키는 해시맵을 하나 만들고 중복이 없는 점들로 볼록 껍질을 구한 다음, 각 점에 대응되는 선수가 유일한지 체크해 가면서 답에 추가해주면 됩니다.
Last updated on