[BOI 2009] Candy Machine

문제: http://www.csc.kth.se/contest/boi/candy.pdf
해법: http://www.csc.kth.se/contest/boi/candy-spoiler.pdf

현재 로봇이 사탕 A(p1,t1) 에서 사탕 B(p2,t2) 로 가는 경우를 고려해보자. (t1 <= t2 가정, p1 -> p2)

(i) p1 <= p2 인 경우

 (p2-p1)+t1 <= t2

 (t1-p1) <= (t2-p2) --- ① 를 만족해야한다.

(ii) p1 > p2 인 경우
 (p1-p2)+t1 <= t2
 (t1+p1) <= (t2+p2) --- ② 를 만족해야한다.

잘 살펴보면 t1 <= t2 라는 가정하에 (i)인 경우 ②를 항상 만족하고, 마찬가지로 (ii)인 경우 ①를 항상 만족한다.

그러므로
(i),(ii)의 경우에 상관없이 두 조건 ①, ②를 만족하면 --- ⓐ
현재 로봇이 사탕 A를 집고 사탕 B를 가지러 갈 수 있다. --- ⓑ
ⓐ, ⓑ는 서로 필요충분조건임을 알 수 있다.
만약 (t1 <= t2) 라는 가정이 없을 때, 즉 (t1 > t2) 라면 두 조건 ①, ②는 동시에 만족할 수 없음도 알 수 있다.

따라서, 문제를 변형 할 수 있는데,
ai = ti+pi, bi = ti-pi 라 했을 때
ai <= aj , bi <= bj 인 경우 한 로봇이 i번 사탕을 집고 j번 사탕을 집으러 갈 수 있다.
ai, bi를 계산해서 각각 구한 뒤, 이 문제는 우리가 평소 잘 알고 있는 문제로 바뀐다. (BOI 2010 - PCB 문제와 유사한 문제)
그 문제는 O(N log N) 만에 해결이 가능하다.

candy machine.cpp