아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

원과 삼각형

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

요약
둘레가 L인 원 위의 서로 다른 n개 점으로 만든 삼각형 중 원의 중심을 내부나 경계에 포함하는 삼각형의 개수를 구한다.
난이도

보통10점 중 7점

유형
투 포인터, 조합론, 기하, 정렬
정답자
아직 제출이 없습니다

문제

길이가 LL인 원 위에 서로 다른 nn개의 점이 주어진다.

이 점들을 꼭짓점으로 하는 삼각형 중에서 원의 중심을 내부나 경계에 포함하는 것의 개수를 구하라.

입력

첫째 줄에 두 정수 nn과 LL이 주어진다 (3≤n≤300 0003 \leq n \leq 300\,000, n≤L≤109n \leq L \leq 10^9).

원 위의 임의의 점을 하나 골라 SS라고 하자. 그러면 원 위의 임의의 점 AA는 0≤x<L0 \le x < L인 xx로 나타낼 수 있는데, xx는 SS에서 AA까지 시계 방향으로 잰 거리이다. 이 수를 AA의 좌표라고 부르자.

둘째 줄에 서로 다른 nn개의 정수 x_1,x_2,…,x_nx\_1, x\_2, \ldots, x\_n이 주어진다. 이는 주어진 점들의 좌표이다 (0≤x_i<L0 \leq x\_i < L).

출력

주어진 점을 꼭짓점으로 하는 삼각형 중에서 원의 중심을 내부나 경계에 포함하는 것의 개수를 정수 하나로 출력한다.

예제2

  1. 예제 1

    입력
    3 10
    0 1 2
    
    예상 출력
    0
    
  2. 예제 2

    입력
    10 10
    0 1 2 3 4 5 6 7 8 9
    
    예상 출력
    60