[UVA][分&二分] 1280 - Curvy Little Bottles＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2013-10-11 08:00:13| 人1,752| 回0 | 上一篇 | 下一篇

[UVA][分&二分] 1280 - Curvy Little Bottles

推 0 收藏 0 0 站台

In her bike rides around Warsaw, Jill happened upon a shop that sold interesting glass bottles. She thought it might make an interesting project to use such bottles for measuring liquids, but this would require placing markings on the bottles to indicate various volumes. Where should those volume marks be placed?

Jill formalized the problem as follows. Assume a bottle is formed by revolving a shape that is the same as the graph of a polynomial P between x = x_low and x = x_high around the x-axis. Thus the x-axis is coincident with a vertical line through the center of the bottle. The bottom of the bottle is formed by a solid circular region at x = x_low , and the top of the bottle, at x = x_high, is left open.

The first sample input represents a bottle formed using the simple polynomial 4 - 0.25x, with x_low = 0 and x_high = 12. The bottom of this bottle is a circle with a radius of 4, and the opening at the top is a circle with a radius of 1. The height of this bottle is 12. Volume markings are in increments of 25.

Given a polynomial P, x_low, x_high, and the volume increment between successive marks on the bottle, compute the distances up from x_low for the marks at successive volume increments. A mark cannot be made past the top of the bottle, and no more than the first 8 increments should be marked. Assume the value of P is greater than zero everywhere between x_low and x_high.

Input

Each test case consists of three lines of bottle data:

Line 1: n, the degree of the polynomial (an integer satisfying 0n10).
Line 2: a₀, a₁,..., a_n, the real coefficients of the polynomial P defining the bottle's shape, where a₀ is the constant term, a₁ is the coefficient of x₁,..., and a_n is the coefficient of x_n. For each i, -100a_i100, and a_n 0.
Line 3:
o
x_low and x_high, the real valued boundaries of the bottle (- 100x_low < x_high100 and x_high - x_low > 0.1).
o
inc, an integer which is the volume increment before each successive mark on the bottle (1inc500).

Output

For each test case, display the case number and the volume of the full bottle on one line. On a second line, display the increasing sequence of no more than 8 successive distances up from the bottom of the bottle for the volume markings. All volumes and height marks should be accurate to two decimal places. If the bottle does not have a volume that allows at least one mark, display the phrase `insufficient volume'. No test case will result in a mark within 0.01 from the top of the bottle. The volume of the bottle will not exceed 1 000. All rounded distances for marks on a bottle differ by at least 0.05.

Sample Input

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

Sample Output

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

目描述：

要你瓶上刻度，而瓶定的方式一在[xlow, xhight] 在 x 上方的多式，
多式著 x 旋而成，xlow 表示杯底部。

每刻度的差指定容量，印出最多前 8 刻度。

目解法：

先解出分方程，integral(p^2 * pi)dx

二分下一指定的刻度。

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;
const double pi = acos(-1);
double calcPoly(double p[], double x, int n) {
 double ret = 0, y = 1;
 int i;
 for(i = 0; i <= n; i++)
 ret += p[i]*y, y *= x;
 return ret;
}
#define eps 1e-8
int main() {
 int n, cases = 0;
 int i, j, k;
 double xlow, xhigh, inc;
 double a[25], b[25], c[25];
 while(scanf("%d", &n) == 1) {
 for(i = 0; i <= n; i++)
 scanf("%lf", &a[i]);
 scanf("%lf %lf %lf", &xlow, &xhigh, &inc);
 memset(b, 0, sizeof(b));// b = a^2
 memset(c, 0, sizeof(c));// c = integral of b.
 for(i = 0; i <= n; i++)
 for(j = 0; j <= n; j++)
 b[i+j] += a[i]*a[j];
 for(i = 0; i <= 2*n; i++)
 c[i+1] = b[i]/(i+1);
 n = 2*n+1;
 double volume = (calcPoly(c, xhigh, n)-calcPoly(c, xlow, n))*pi;
 printf("Case %d: %.2lf\n", ++cases, volume);
 int marking = min((int)floor(volume/inc), 8);
 if(marking == 0)
 puts("insufficient volume");
 else {
 double prev = xlow;
 for(i = 0; i < marking; i++) {
 double l = prev, r = xhigh, mid;
 double lv = calcPoly(c, l, n), mv;
 while(fabs(l-r) > eps) {
 mid = (l+r)/2;
 mv = calcPoly(c, mid, n);
 if((mv-lv)*pi > inc)
 r = mid;
 else
 l = mid;
 }
 if(i) putchar(' ');
 printf("%.2lf", mid-xlow);
 prev = mid;
 }
 puts("");
 }
 }
 return 0;
}