Informatica Online Judge

  다차원 척도법 [2137 / 0859]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[34th 정승민]
Writer ID : [gs16099]

Background

모 고등학교의 영어 교사인 하스미 세이지 선생님은 학생들의 설문조사 결과를 바탕으로 인간관계를 다차원척도법(Multidimensional Scaling, MDS)으로 2차원 평면에 나타내었다.

그리고, 신학년에 서로 어색한 학생들을 위해서 학생들을 친구로 묶어 주려고 한다. 그러나 두 명을 친구로 만드는 것이 쉬운 것만은 아니다. 두 명을 친구로 만들 때 필요한 (정신적)에너지는 두 학생 사이의 택시 거리와 같다.

최소한의 에너지로 모든 학생을 직,간접적인 친구 관계로 연결한 선생님은, 몹시 귀찮은 듯한 표정을 지으며 일을 수월하게 만들 아이디어를 떠올렸다.

-지금 연결된 상태를 기본으로, 학생들의 연결 관계가 분리되지 않는 선에서 학생을 한 명 졸업시킨다고 하면, 모두 연결하는 데 필요한 에너지가 줄어드는군.-

하지만 학교 규정상 먼저 졸업하는 것은 불가능하기 때문에, 선생님이 직접 손을 써야 한다. 학생을 졸업시킬 때는 (육체적)에너지가 필요하다.

졸업시키면 에너지의 이득을 볼 수 있는 학생의 수를 구하여라.

Input

첫 줄에 학생의 수 n ( 3 ≤ n ≤ 1,500 )과 졸업시키는 데 필요한 에너지 k ( 0 ≤ k ≤ 100 )가 입력된다.
두 번째 줄부터 n줄에 걸쳐 학생의 x와 y 좌표( -100 ≤ x,y ≤ 100 )가 공백으로 분리되어 입력된다. 서로 다른 학생은 위치가 다르다는 것이 보장된다.

Output

졸업시키면 이득을 볼 수 있는 학생의 수를 출력한다.

IO Example

입력1
3 10
1 1
2 2
3 3

출력1
0

입력2
3 1
1 1
2 2
3 3

출력2
2

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]