[PS] 2013 Daejeon 6505 Metal

본 문제는 메탈(쇠구슬)의 좌표가 주어진다.

우리는 수평터널을 만들수 있다.

수평터널을 지나면서 메탈을 수집하는데, 가장 효율적으로 수평터널을 팠을때

가장 수집길이가 긴 메탈의 길이를 출력하는 문제이다.

N K
x1 y1 x2 y2...

와 같이 입력이 들어올때 K는 수직 엘리베이터의 수이다.

즉 K가 1이면 수평터널을 2개 만들수 있다.

먼저 Y를 기준으로 가장큰 Y와 가장작은 Y의 차를 구한다.

이 차를 C 라고 한다면

정답은 0

이 범위를 이분탐색을 통해 정답을 찾으면된다.

자 그럼 정답을 찾는 방법은

먼저 X축을 기준으로 정렬된 좌표배열 V를 얻는다.

메탈의수집길이 m이 있을때

V[i].y - m ~ V[i].y+m 까지 구간으로 직선이 몇개나 그어지는지 확인하면된다.
위와 같이 메탈이있을떄 빨간선처럼 범위를 지정하면 총 몇개의 수평터널이

만들어 지는지 확인할 수 있다.