곡선 모양의 작은 병

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

요약
회전체로 만든 병의 부피가 주어진 증가량에 도달하는 x 위치를 최대 8개까지 구하는 문제다.
난이도

보통10점 중 5점

유형
수학, 이분 탐색, 구현, 누적 합
정답자
아직 제출이 없습니다

문제

질(Jill)은 바르샤바를 자전거로 돌아다니다가 흥미로운 유리병을 파는 가게를 발견했다. 그녀는 이런 병으로 액체의 양을 재는 재미있는 프로젝트를 떠올렸지만, 그러려면 여러 부피를 나타내는 눈금을 병에 새겨야 했다. 그 부피 눈금은 어디에 새겨야 할까?

질은 문제를 다음과 같이 정리했다. 병은 다항식 PP의 그래프 아래 영역을 x=xlowx = x_{low}부터 x=xhighx = x_{high}까지 xx축을 중심으로 회전시켜 만든다. 따라서 xx축은 병의 중심을 지나는 수직선과 일치한다. 병의 바닥은 x=xlowx = x_{low}에 있는 꽉 찬 원판이고, x=xhighx = x_{high}에 있는 병의 윗부분은 뚫려 있다. xlowx_{low}와 xhighx_{high} 사이에서 PP의 값은 항상 0보다 크다.

xlowx_{low}부터 높이 xx까지의 병의 부피는 ∫xlowxπ P(t)2 dt\int_{x_{low}}^{x} \pi\,P(t)^2\,dt이다. 예를 들어 P(x)=4−0.25xP(x) = 4 - 0.25x, xlow=0x_{low} = 0, xhigh=12x_{high} = 12로 만든 병은 바닥 원의 반지름이 44, 윗부분 구멍의 반지름이 11, 높이가 1212이다.

다항식 PP, 경계 xlowx_{low}와 xhighx_{high}, 그리고 눈금 사이의 부피 증가량이 주어질 때, 연속한 부피 증가량마다 새길 눈금의 xlowx_{low}로부터의 높이를 구하라. 눈금은 병의 윗부분을 넘어서 새길 수 없으며, 처음 88개의 증가량까지만 새긴다.

입력

입력에는 여러 개의 테스트 케이스가 파일의 끝까지 이어서 주어진다. 각 테스트 케이스는 병 데이터를 나타내는 세 줄로 이루어진다.

  • 첫째 줄: 다항식의 차수 nn. 0≤n≤100 \le n \le 10인 정수이다.
  • 둘째 줄: 다항식 PP의 실수 계수 a0,a1,…,ana_0, a_1, \ldots, a_n. 여기서 a0a_0는 상수항이고 aia_i는 xix^i의 계수이다. 모든 ii에 대해 −100≤ai≤100-100 \le a_i \le 100이며, an≠0a_n \ne 0이다.
  • 셋째 줄: 병의 경계인 두 실수 xlowx_{low}와 xhighx_{high}(−100≤xlow<xhigh≤100-100 \le x_{low} < x_{high} \le 100, xhigh−xlow>0.1x_{high} - x_{low} > 0.1)에 이어, 연속한 눈금 사이의 부피 증가량 incinc(1≤inc≤5001 \le inc \le 500인 정수)가 주어진다.

출력

각 테스트 케이스마다 두 줄을 출력한다. 첫째 줄에는 케이스 번호와 병 전체의 부피를 Case k: V 형식으로 출력한다. 둘째 줄에는 부피 눈금에 대한, 병 바닥으로부터의 높이를 나타내는 최대 88개의 증가하는 거리 값을 공백 하나로 구분하여 출력한다. 모든 부피와 거리는 소수점 아래 두 자리까지 정확해야 한다. 병의 부피가 눈금 하나를 새기기에도 부족하면, 둘째 줄에 대신 insufficient volume을 출력한다.

어떤 눈금도 병 윗부분에서 0.010.01 이내에 놓이지 않고, 병의 부피는 10001000을 넘지 않으며, 한 병에서 반올림한 눈금 거리들은 서로 적어도 0.050.05만큼 차이가 남이 보장된다.

예제1

  1. 예제 1

    입력
    1
    4.0 -0.25
    0.0 12.0 25
    1
    4.0 -0.25
    0.0 12.0 300
    0
    1.7841241161782
    5.0 10.0 20
    0
    1.0
    0.0 10.0 10
    
    예상 출력
    Case 1: 263.89
    0.51 1.06 1.66 2.31 3.02 3.83 4.75 5.87
    Case 2: 263.89
    insufficient volume
    Case 3: 50.00
    2.00 4.00
    Case 4: 31.42
    3.18 6.37 9.55