레이팅 미적용농부 존이 가장 싫어하는 농장 일 중 하나는 소똥을 잔뜩 실어 나르는 것이다. 이 과정을 간소화하기 위해 그는 흥미로운 아이디어를 생각해 냈다. 트랙터 뒤에 수레를 달고 두 지점 사이에서 소똥을 실어 나르는 대신, 거대한 소똥 새총으로 공중으로 쏘아 보내면 어떨까? (과연, 무슨 일이 잘못될 수 있겠는가...)
농부 존의 농장은 하나의 길고 곧은 도로를 따라 지어져 있어서, 농장의 어떤 위치든 이 도로 상의 위치(사실상 수직선 위의 한 점)만으로 간단히 나타낼 수 있다. 농부 존은 \(N\)개의 새총을 만든다 (\(1 \leq N \leq 10^5\)). \(i\)번째 새총은 세 정수 \(x_i\), \(y_i\), \(t_i\)로 표현되며, 이 새총이 소똥을 위치 \(x_i\)에서 위치 \(y_i\)까지 단 \(t_i\) 단위의 시간 만에 쏘아 보낼 수 있음을 뜻한다.
농부 존에게는 운반해야 할 소똥 더미가 \(M\)개 있다 (\(1 \leq M \leq 10^5\)). \(j\)번째 더미는 위치 \(a_j\)에서 위치 \(b_j\)로 옮겨야 한다. 트랙터로 소똥을 거리 \(d\)만큼 실어 나르는 데는 \(d\) 단위의 시간이 걸린다. 농부 존은 각 소똥 더미의 운반에 어떤 새총이든 최대 한 번 사용할 수 있게 하여 이 시간을 줄이고 싶다. 농부 존이 소똥을 싣지 않고 트랙터를 이동시키는 시간은 계산에 넣지 않는다.
\(M\)개의 소똥 더미 각각에 대해, 운반 과정에서 새총을 최대 한 번 사용할 수 있을 때 가능한 최소 운반 시간을 구하도록 농부 존을 도와주자.
출제자: Brian Dean
출제자: Brian Dean
입력의 첫째 줄에 \(N\)과 \(M\)이 주어진다. 다음 \(N\)개의 줄에는 각각 새총 하나가 정수 \(x_i\), \(y_i\), \(t_i\)로 주어진다 (\(0 \leq x_i, y_i, t_i \leq 10^9\)). 마지막 \(M\)개의 줄에는 옮겨야 하는 소똥 더미들이 정수 \(a_j\)와 \(b_j\)로 주어진다.
각 소똥 더미에 대해 하나씩, 그 더미를 운반하는 데 필요한 최소 시간을 나타내는 \(M\)개의 줄을 출력한다.
slingshot.in · 출력을 쓸 파일 slingshot.out2 3
0 10 1
13 8 2
1 12
5 2
20 74
3
10Here, the first pile of manure needs to move from position 1 to position 12.
Without using an slingshot, this would take 11 units of time. However, using
the first slingshot, it takes 1 unit of time to move to position 0 (the
slingshot source), 1 unit of time to fling the manure through the air to land at
position 10 (the slingshot destination), and then 2 units of time to move the
manure to position 12. The second pile of manure is best moved without any
slingshot, and the third pile of manure should be moved using the second
slingshot.
riseoj 작성
출처 올림피아드 > USACO > 2017-2018 > February > Platinum