옛날 옛적에, GS왕국은 현명한 왕 준혁이에 의해 통치되고 있었어요.

17년간의 재위 기간 이후, 성공적인 수많은 전쟁과 능숙한 정치에 의해,

GS왕국은 2차원 좌표평면이 되었어요.

2차원 좌표평면 형태의 왕국은 경계가 없어 여행이 매우 간편해졌어요.

왕국의 큰 기념일이 다가왔어요! 왕국에는 사람들이 모일 수 있는 N개의 광장이 있어요.

준혁이는 그의 백성을 더 가까이서 살펴보고 싶었기에, 그는 광장 사이의 여행을 계획했어요.

준혁이는 방문하는 광장들에서 연설을 할 거에요.

처음에는, 준혁이는 p₁ → p₂ → ... → p_n의 경로로 이동하고자 했어요.

그러나, 늙고 지친 준혁이는 너무나도 긴 여행을 견디지 못할거 같아요.

그래서, 준혁이의 보좌관 은수는 몇 개의 광장을 건너뛰기로 했어요.

새로운 여행 계획은 p_i1 → p_i2 → ... → p_im의 경로로 표현돼요.

(1 = i₁ < i₂ < ... < i_m = n)

하지만, 준혁이는 p_j에서 선분 p_ik -> p_ik+1 까지의 거리가 D를 초과할 경우 광장 j를 절대 건너뛰지 않을거에요. (i_k < j < i_k+1)

은수는 늙고 지친 준혁이를 걱정해서, 준혁이가 방문하는 광장의 수를 최소화시키고 싶어 해요.

여러분이 은수를 도와, 준혁이의 새로운 여행 경로를 찾는 것을 도와주세요.

왕국 여행 timer 2s memory 256MB

왕국 여행 2s 256MB