maximum independent set1 ACM ICPC World Finals 2014 - Sensor Network ACM ICPC 2014 World Finals I번 - 문제 링크답이 되는 원을 생각해보자. 거기엔 가장 먼 두 점이 있다. 우리는 두 점을 결정해 볼 수 있다.점 A와 B를 결정했고, 그 둘 사이의 거리는 선분 AB의 길이가 된다. 물론 이 선분의 길이는 주어진 d값보다 작거나 같아야겠다. 점 A를 중심으로 선분 AB의 길이(R)만큼의 반지름을 가지는 원과 점 B를 중심으로 길이 R의 반지름을 가지는 원을 생각해볼 수 있다. 어떤 점들이 이 두 원의 교집합 안에 속한다면, 점 A와 점 B로부터 거리가 R 이하인 것이다. 하지만, 위의 그림에서 볼 수 있듯이 내부의 점들 사이의 거리는 R보다 더 클 수 있다. 따라서 이 점들 중 최소개수의 점들을 제거해서 서로 간의 거리가 모두 R이하가 되도록 해야한다.. 2016. 4. 23. 이전 1 다음