908C New Year and Curling

2차원평면에서 원의 방정식 응용 문제

컬링 게임을 하는데 컬링이 y=0인 지점부터 차곡차곡 쌓인다. 

컬링은 x가 주어졌을때 (x, 10^100) 인 지점부터 y=0인 지점으로 가며 경로상에 동일한 컬링이 있을때 그곳에 부딪히고 멈춘다.

입력이 주어진것부터 컬링을 하는것이며,

인풋이 아래와 같을때 그림은 대충 저렇다.

6 2
5 5 6 8 3 12

그런데 쌓이는 상태를 어떻게 저장해줘야 새로운 컬링을 그곳에 부딪힌다는 생각을 할 수 있기 때문에,

나는 이 곳에서 막혔었다.

하지만 생각해보면 결국은 이미 사용한 컬링들은 (x,y) 를 저장하고 다음 새 컬링이 올때 그것을 참조하면된다.

그렇담 y는 어떻게 결정되는가?

두 원이 접하기 위해선 다음과같은 방정식을 만족해야한다.

두 원의 반지름의 합 = 두 원의 원점 사이의 거리

따라서 x1, y1을 기존에 있던 원, x2, y2을 새로운 원이라하자.  이때 x1, y1, x2는 알고있다. 따라서

y2를 기준으로 식을 이항시킬것이다.

2 * r = sqrt( (x1-x2)^2 + (y1- y2)^2) 이며

4r^2 = (x1-x2)^2 + (y1-y2)^2

4r^2-(x1-x2)^2 = (y1-y2)^2

y2 = y1+-root( 4r^2 - (x1-x2)^2)

이다.

이때 y2는 y1보다 무조건 커야하므로 ( 왜냐하면 컬링은 항상 쌓이므로 기존의 컬링 좌표보다 높아야한다.)

y2= y1 +root( 4r^2 - (x1-x2)^2 ) 이다.

따라서 우리는 새로운 원의 y2를 구할수 있었다.

그뒤 컬링의 물리적인 이유이때문에 기존의 원 중에서 만났을 때 새로운 원의 원점이 가장 높으곳에 있어야 하기때문에 모든 기존의 원에 대해 y2를 연산하고 max만을 저장해준다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/cf/math/908C.c