Accurate Curve Fitting

Many thanks to Clive Fraser for creating this problem!

A curve is often represented by a series of straight line segments. If there are sufficient of these, the series of straight lines can look indistinguishable from the curve. If we think of the problem of representing a given curve by a series of straight line segments, it is natural to ask the question "How well does this series of line segments represent the curve and, could we achieve a better representation with the same number of line segments?"

A better representation will have the line segments closer to the curve. This means that the sum of the areas between the line segments and the curve will be smaller. This leads immediately to a criterion for the most accurate fit. We simply need to minimise the sum of the areas between the line segments and the curve.

In this problem we will use the curve y = x^4. The curve passes through the origin and is always above or touching the x-axis. The diagram, which shows the curve in blue, is not intended to be an accurate representation of this curve but is merely an illustration of the problem. We will be given two points A and -A which lie on the curve. We will also be given a number N. This is the number of points (including A and -A) which are to be used in defining the line segments. In the diagram N = 4, which means that we have N-1 = 3 line segments with which to represent the curve. The 4 points on the curve are shown in red and the 3 line segments, also in red, are drawn between them. The 2 points A and -A are fixed but the remaining 2 points can be placed anywhere on the curve between A and -A. The diagram shows a possible starting position for these. The problem now is to find the positions for these 2 points which will minimise the sum of the areas between the 3 line segments and the curve.

Clearly we need to be able to calculate this area from the coordinates of each of the 4 points. This can be done as follows. The area shown in yellow on the diagram is bounded below by the x-axis and above by the 3 line segments. The boundaries to the right and left are just the perpendiculars dropped from the points A and -A to the x-axis. It should be obvious that the area is easily subdivided into a number of triangles and rectangles, so it is easy to calculate. If we now subtract from this, the area below the curve (between the points -A and A) we will obtain the required sum of the areas between the line segments and the curve.

However, it should be obvious that the area below the curve (between the points -A and A) remains constant and does not change when the positions of the 2 intermediate points are changed. This means that the minimum area between the curve and the 3 line segments occurs when the area in yellow is at a minimum. Since this area is easy to calculate from the coordinates of the 4 points, we will use the criterion of minimising the area in yellow as the goal to be achieved in producing the best curve fit for N points.

In the problem you will be given the number of points N and an x-coordinate X0. The point A will have an x-coordinate of X0 while the point -A will have an x-coordinate of -X0. The problem is then to minimise the area shown in yellow by distributing the N-2 points between A and -A such that the N-1 line segments represent the best fit to the curve, using this criterion.

In the example above we have N = 4. Suppose that X0 = 1.5. We now know that the coordinates of the point A are (1.5, 5.0625) and the coordinates of the point -A are (-1.5, 5.0625). Note that 1.5^4 = 5.0625. The two intermediate points can be placed anywhere between A and -A. We need to find a way of doing this which minimises the area in yellow. For this example, the minimum size of the area in yellow is 4.48575382 (rounded to 8 decimal places). For interest, the sum of the areas between the line segments and the curve is 1.44825382; although this is not a required part of the problem. Clearly, with only 4 points, we cannot get a very close approximation to the curve. However, as the number of points increases we can get closer and closer to the curve, making the area between the curve and the line segments considerably smaller.

In the actual problem, the number of points N will vary between 91 and 111. The value of X0 will vary between 1.0 and 2.0. The first two examples given below are intended for testing your algorithm, so have smaller values of N. The third is a typical problem.

Input/Output description: The first and only line of the input data will contain the values N and X0, where N is an integer representing the number of points on the curve and X0 is a real number representing the x-coordinate of point A. Find the minimum size for the area in yellow. Give this answer rounded to 8 decimal places.

Example 1:

input:
4 1.5

answer:
4.48575382

Example 2:

input:
10 1.8

answer:
7.96155001

Example 3:

input:
97 1.123

answer:
0.71476355