## Bezier CurvesProblem #78 |

Bezier curves are shapes very popular in computer design. They could be found among instruments in almost any
image editor, including **Microsoft Paint** presented with any version of **Windows**.

Initially they were invented by engineers working on design of car bodies at automobile industry. Now we will try to learn how to create such curves programmatically.

**Algorithm**

The curve is defined by starting, ending and several intermediate points. The example above have `4`

points - i.e.
only `2`

intermediate.

At first step we draw a **polyline** between these points, from starting via all intermediate in order to the ending
one. It is shown with thin grey line at the picture.

Now suppose we choose some parameter `alpha`

in range `0 ... 1`

and divide each segment of the polyline according
to it, i.e. in ratio:

```
alpha : (1 - alpha)
```

For example, in the drawing above `alpha = 0.333`

.

For polyline drawn between `N`

points and consisting of `N - 1`

segments we get `N - 1`

new points - they are shown
as small purple dots at the leftmost picture.

Let us link these new points with new polyline, consisting of `N - 2`

segments. It is shown as thin blue line at
the central and right-most pictures.

Then we can divide these new segments with the same ratio `alpha`

once more. So we build a third polyline (shown in
green at the rightmost picture).

We will continue building polylines until we get the last one consisting of only one segment. When we divide it with
the ratio `alpha`

, we get a single point.

This last point is the point of the Bezier Curve corresponding to parameter `alpha`

.

The remaining is simple - just repeat these steps for different values of `alpha`

- for example:

```
alpha = 0.00, 0.01, 0.02, 0.03, ... , 0.98, 0.99, 1.00
```

So that for example with `101`

value (from `0`

to `1`

with the step of `0.01`

) we get the same amount of points,
placed closely enough to each other. Connecting them we get the smooth curve (thick grey line at the rightmost
picture).

Please refer to wikipedia article for more examples and animated demo.

**Input data** will contain the number of initial points `M`

and the number `N`

of values for parameter `alpha`

.

Next `M`

lines will contain coordinates of one initial point each (`X`

and `Y`

).

**Answer** should contain `N`

pairs of coordinates (also `X`

and `Y`

) for all calculated points lying on the given
curve. Pairs and points in them should be separated simply by space. Coordinates should be rounded to nearest
integer (because when we do graphics coordinates of pixels are of course integer).

**Note:** the values for `alpha`

should be calculated by dividing the range `0.0 ... 1.0`

into `N - 1`

equal steps.

Example:

```
input data:
4 10
0 180
90 0
180 120
270 60
answer:
0 180 30 130 60 99 90 82 120 76 150 75 180 78 210 79 240 74 270 60
```

**Additional Exercise** for your own amusement - try to draw the resulting curve by the points which you calculated
using graphical instruments of your favorite programming language. Or you can do this loading these points into
`Microsoft Excel`

(`Openoffice Calc`

) and drawing `XY`

chart by them.

You need to login to get test data and submit solution.