19470 Physics

문제 링크
질량이 같은 n개의 공의 초기 속력, 위치, 방향이 주어질 때, t초 후 k번째로 속력이 작은 공의 속력을 출력하는 쿼리를 처리하는 문제이다.

주목할 만한 포인트는 공이 항상 a_i*v_i=C를 만족하면서 움직인다는 것인데, t에 대해 적분해 주면 공의 속도 v_i=sqrt(2Ct)+v0_i로 표현될 수 있다. 거기에다 공들은 서로 완전 탄성 충돌한다는 조건이 붙어 있는데, 질량이 같은 두 물체가 정면으로 완전 탄성 충돌하면 속도가 서로 교환된다. 즉 공 간의 충돌은 결과에 영향을 줄 수 없다.

따라서 우리는 공들의 속력만을 받아와 정렬한 뒤, v[k]를 위의 식의 v0_i에 대입하여 답을 구할 수 있다.

import sys
input = sys.stdin.readline
N,C = map(int,input().split())
v = sorted([int(input().split()[0]) for _ in range(N)])
for _ in range(int(input())):
    t,k = map(int,input().split())
    print((v[k-1]**2+2*C*t)**0.5)

언뜻 보면 공들의 충돌을 일일이 체크해야 되는 복잡한 문제처럼 보이지만, 잘 생각해 보면 짧은 코드만으로 문제를 해결할 수 있다.