Expected Distance

시간 제한1초메모리 제한2048 MB

요약
원 위에 놓인 n명의 친구에 대해, 모든 친구를 한 반평면에 담을 수 없는 '좋은 점'에서 가장 가까운 k번째 친구까지의 평균 거리를 구한다.
난이도

어려움10점 중 9점

유형
기하, 확률, 수학, 이분 탐색
정답자
아직 제출이 없습니다

문제

Svetozar is passionate about robotics. He loves to test his robots on a flat, perfectly round platform in his backyard. Today, he invited nn of his friends and positioned each of them at the edge of this platform (that is, on the circumference), each at different points.

Svetozar is now planning to position his new robot at some good point on the platform, and then command it to determine the kk-th closest friend to the robot (if there are several, choose any) and walk straight to that friend. Svetozar calls a point on the platform good if there is no half-plane containing all his friends, the boundary of which passes through the given point.

Now Svetozar is interested in the expected distance the robot will travel if its initial point is equally likely to be chosen from all good points.

입력

The first line contains two integers nn and kk (3≤n≤1003 \leq n \leq 100, 1≤k≤n1 \leq k \leq n): the number of Svetozar's friends involved, and the parameter for the robot.

The second line contains nn integers a_1,a_2,…,a_na\_1, a\_2, \ldots, a\_n (0≤a_i<360⋅1030 \leq a\_i < 360 \cdot 10^3, a_i≠a_ja\_i \ne a\_j for i≠ji \ne j). Here, a_ia\_i denotes the angle between the direction to the north and the direction from the center of the platform to Svetozar's ii-th friend counterclockwise, in thousandths of a degree.

출력

Print a single real number: the expected distance, measured in radii of platform. The answer will be considered correct if its absolute or relative error does not exceed 10−410^{-4}.

예제5

  1. 예제 1

    입력
    3 1
    2023 122023 242023
    
    예상 출력
    0.607986406
    
  2. 예제 2

    입력
    3 2
    122023 242023 2023
    
    예상 출력
    1.174556945
    
  3. 예제 3

    입력
    3 3
    242023 2023 122023
    
    예상 출력
    1.376646683
    
  4. 예제 4

    입력
    9 9
    8 24 43 539 982 4435 39982 44353 99824
    
    예상 출력
    1.046471608
    
  5. 예제 5

    입력
    3 1
    998 244 353
    
    예상 출력
    0.002476278