시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 128 | 95 | 70 | 79.545% |
이차 함수 $f(x) = (x-a)(x-b)$가 주어진다.
좌표평면 상의 $y = f(x)$ 그래프 위에 $a = x_0 < x_1 < x_2 <\cdots < x_n = b$ 이도록 $n+1$개의 점 $(x_0,f(x_0)),(x_1,f(x_1)),\cdots,(x_n,f(x_n))$을 찍을 때, 이 $n+1$개의 점들로 만들어지는 볼록다각형 넓이의 최댓값을 구하시오.
모든 입력에 대해 정답은 항상 유리수임을 증명할 수 있다.
첫째 줄에 정수 $n$이 주어진다. ($2 \leq n \leq 1\,000$)
둘째 줄에 두 정수 $a, b$가 주어진다. ($0 \leq a < b \leq 1\,000$)
다각형 넓이의 최댓값이 $\displaystyle \frac{p}{q}$($p$와 $q$는 서로소인 자연수)일 때, $q\cdot v\equiv p (\bmod 1\,000\,000\,007$)이 되는 $0$이상 $1\,000\,000\,006$ 이하의 정수 $v$를 출력한다.
모든 입력에 대해 이러한 $v$가 항상 존재함이 보장된다.
3 0 3
4
2 0 1
125000001
13 17 99
361038099
Camp > 숭고한 연합 Algorithm Camp > 2022 숭고한 연합 알고리즘 콘테스트 > Division 1 B번