28762번 - Поместье мафии
문제
고담에서 가장 강력한 마피아 가문의 두목인 당신은 이제 은퇴할 때가 되었습니다. 아들들에게 두목 지위와 재산을 물려주려 합니다. 당신의 재산은 길이가 $l$킬로미터인 폭이 일정한 토지이며, 길이 $l$인 선분으로 나타낼 수 있습니다.
$n$명의 아들들은 각각 당신의 토지 위에 저택을 가지고 있습니다. $i$번째 아들의 저택은 은 토지의 왼쪽 끝으로부터 $a_i$킬로미터 떨어진 곳에 있습니다. 물론 두 개의 저택이 같은 지점에 위치하는 경우는 없습니다.
당신은 당신의 토지를 $n$개의 연속된 부분으로 나누어 아들들이 각각 자신의 저택이 포함된 연속된 부분을 가지도록 모든 토지를 나누어 주기로 하였습니다.
토지의 부분의 경계선에 저택이 위치해도 저택이 그 부분에 포함된 것으로 생각합니다.
분할을 최대한 공평하게 하기 위해 당신은 가장 토지를 많이 받는 아들에게 나누어주는 토지의 길이를 최소화해야 한다고 결정했습니다. 이 값을 구해 봅시다.
입력
첫 번째 줄에는 두 개의 정수 $n$과 $l$이 포함됩니다.
마피아 보스의 아들 수와 재산 길이($2 \le n \le 100\,000$, $1 \le l \le 10^9$)입니다.
두 번째 줄에는 아들들의 저택 위치를 나타내는 $n$개의 정수 $a_i$ ($0 \le a_i \le l$). $ i \ne j $ 이면 $a_i \ne a_j$ 인 데이터만 주어집니다.
출력
최적 분할에서 가장 긴 부분의 길이를 실수로 출력합니다. 절대 또는 상대 오차는 $10^{-6}$까지 허용됩니다.
댓글을 작성하려면 로그인해야 합니다.
iktk 2년 전
문제
고담에서 가장 강력한 마피아 가문의 두목인 당신은 이제 은퇴할 때가 되었습니다. 아들들에게 두목 지위와 재산을 물려주려 합니다. 당신의 재산은 길이가 $l$킬로미터인 폭이 일정한 토지이며, 길이 $l$인 선분으로 나타낼 수 있습니다.
$n$명의 아들들은 각각 당신의 토지 위에 저택을 가지고 있습니다. $i$번째 아들의 저택은 은 토지의 왼쪽 끝으로부터 $a_i$킬로미터 떨어진 곳에 있습니다. 물론 두 개의 저택이 같은 지점에 위치하는 경우는 없습니다.
당신은 당신의 토지를 $n$개의 연속된 부분으로 나누어 아들들이 각각 자신의 저택이 포함된 연속된 부분을 가지도록 모든 토지를 나누어 주기로 하였습니다.
토지의 부분의 경계선에 저택이 위치해도 저택이 그 부분에 포함된 것으로 생각합니다.
분할을 최대한 공평하게 하기 위해 당신은 가장 토지를 많이 받는 아들에게 나누어주는 토지의 길이를 최소화해야 한다고 결정했습니다. 이 값을 구해 봅시다.
입력
첫 번째 줄에는 두 개의 정수 $n$과 $l$이 포함됩니다.
마피아 보스의 아들 수와 재산 길이($2 \le n \le 100\,000$, $1 \le l \le 10^9$)입니다.
두 번째 줄에는 아들들의 저택 위치를 나타내는 $n$개의 정수 $a_i$ ($0 \le a_i \le l$). $ i \ne j $ 이면 $a_i \ne a_j$ 인 데이터만 주어집니다.
출력
최적 분할에서 가장 긴 부분의 길이를 실수로 출력합니다. 절대 또는 상대 오차는 $10^{-6}$까지 허용됩니다.