algospot 핀볼 시뮬레이션(문제 ID: PINBALL)

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/PINBALL

algospot.com :: PINBALL

공의 처음 위치와 진행방향과 원형태의 장애물들이 주어졌을때 공이 몇번 장애물에서 튕겨졌는지 순서대로 출력하는 문제이다.

공의 크기를 고려하는 대신에 장애물들의 반지름을 1씩 늘려서 문제를 해결 해보자

공이 처음위치 p에서 1초에 d만큼 굴러간다 하면 f(t) = p+td로 표현할 수 있다. 그럼 중심이 c이고 반지름이 r인 장애물과 교차하는 시간은 다음 식을 이용해 구할 수 있다.

|c-f(t)| = r       양변을 제곱하여 전개하면(dot를 내적이라 하면)

d(dot)dt^2 + 2(p-c)(dot)dt + c(dot)c+p(dot)p-2(c(dot)p)-r^2=0

이때 t는 항상 양수여야 하고 실근이 두개 반환될 때에는 둘중 작은값이 장애물과 부딪히는 시간이라는것은 직관적으로 알 수 있다.

t를 통해 구한 충돌지점(contact)을 이용하여 -dir을 contact-center에 사영시키고 해당 벡터를 d`라고 하자

2(dir+d`)-dir = dir+2d`이 충돌지점에서 장애물에 부딪힌 후 공의 진행방향이다.

 

코드원본: https://github.com/sbl133/JongmanBook/blob/main/15.%20ComputationalGeometry/PINBALL.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1