// TBezierInterpolation.cpp
#include <vector>
#include <iostream>
#include <cmath>
 
using namespace std;
 
#define EPSILON 1.0e-5
#define RESOLUTION 32
 
class Point2D
{
public:
    double x, y;
 
    Point2D() { x = y = 0.0; };
    Point2D(double _x, double _y) { x = _x; y = _y; };
 
    Point2D operator +(const Point2D &point) const { return Point2D(x + point.x, y + point.y); };
    Point2D operator -(const Point2D &point) const { return Point2D(x - point.x, y - point.y); };
    Point2D operator *(double v) const { return Point2D(x * v, y * v); };
    void operator +=(const Point2D &point) { x += point.x; y += point.y; };
    void operator -=(const Point2D &point) { x -= point.x; y -= point.y; };
 
    void normalize()
    {
        double l = sqrt(x * x + y * y);
        x /= l;
        y /= l;
    }
};
 
class Segment
{
public:
    Point2D points[4];
 
    void calc(double t, Point2D &p)
    {
        double t2 = t * t;
        double t3 = t2 * t;
        double nt = 1.0 - t;
        double nt2 = nt * nt;
        double nt3 = nt2 * nt;
        p.x = nt3 * points[0].x + 3.0 * t * nt2 * points[1].x + 3.0 * t2 * nt * points[2].x + t3 * points[3].x;
        p.y = nt3 * points[0].y + 3.0 * t * nt2 * points[1].y + 3.0 * t2 * nt * points[2].y + t3 * points[3].y;
    };
};
 
bool calculateSpline(const vector<Point2D> &values, vector<Segment> &bezier)
{
    int n = values.size() - 1;
 
    if (n < 2)
        return false;
 
    bezier.resize(n);
 
    Point2D tgL;
    Point2D tgR;
    Point2D cur;
    Point2D next = values[1] - values[0];
    next.normalize();
 
    double l1, l2, tmp, x;
 
    --n;
 
    for (int i = 0; i < n; ++i)
    {
        bezier[i].points[0] = bezier[i].points[1] = values[i];
        bezier[i].points[2] = bezier[i].points[3] = values[i + 1];
 
        cur = next;
        next = values[i + 2] - values[i + 1];
        next.normalize();
 
        tgL = tgR;
 
        tgR = cur + next;
        tgR.normalize();
 
        if (abs(values[i + 1].y - values[i].y) < EPSILON)
        {
            l1 = l2 = 0.0;
        }
        else
        {
            tmp = values[i + 1].x - values[i].x;
            l1 = abs(tgL.x) > EPSILON ? tmp / (2.0 * tgL.x) : 1.0;
            l2 = abs(tgR.x) > EPSILON ? tmp / (2.0 * tgR.x) : 1.0;
        }
 
        if (abs(tgL.x) > EPSILON && abs(tgR.x) > EPSILON)
        {
            tmp = tgL.y / tgL.x - tgR.y / tgR.x;
            if (abs(tmp) > EPSILON)
            {
                x = (values[i + 1].y - tgR.y / tgR.x * values[i + 1].x - values[i].y + tgL.y / tgL.x * values[i].x) / tmp;
                if (x > values[i].x && x < values[i + 1].x)
                {
                    if (tgL.y > 0.0)
                    {
                        if (l1 > l2)
                            l1 = 0.0;
                        else
                            l2 = 0.0;
                    }
                    else
                    {
                        if (l1 < l2)
                            l1 = 0.0;
                        else
                            l2 = 0.0;
                    }
                }
            }
        }
 
        bezier[i].points[1] += tgL * l1;
        bezier[i].points[2] -= tgR * l2;
    }
 
    l1 = abs(tgL.x) > EPSILON ? (values[n + 1].x - values[n].x) / (2.0 * tgL.x) : 1.0;
 
    bezier[n].points[0] = bezier[n].points[1] = values[n];
    bezier[n].points[2] = bezier[n].points[3] = values[n + 1];
    bezier[n].points[1] += tgR * l1;
 
    return true;
}
 
int main()
{
    vector<Point2D> testValues;
    vector<Segment> spline;
    Point2D p;
 
    testValues.push_back(Point2D(0, 0));
    testValues.push_back(Point2D(20, 0));
    testValues.push_back(Point2D(45, -47));
    testValues.push_back(Point2D(53, 335));
    testValues.push_back(Point2D(57, 26));
    testValues.push_back(Point2D(62, 387));
    testValues.push_back(Point2D(74, 104));
    testValues.push_back(Point2D(89, 0));
    testValues.push_back(Point2D(95, 100));
    testValues.push_back(Point2D(100, 0));
 
    calculateSpline(testValues, spline);
 
    for (auto s : spline)
    {
        for (int i = 0; i < RESOLUTION; ++i)
        {
            s.calc((double)i / (double)RESOLUTION, p);
            cout << p.x << " " << p.y << endl;
        }
    }
 
    cout << testValues.back().x << " " << testValues.back().y << endl;
 
    return 0;
}

CgovLyBUQmV6aWVySW50ZXJwb2xhdGlvbi5jcHAKI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+CiAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKIAojZGVmaW5lIEVQU0lMT04gMS4wZS01CiNkZWZpbmUgUkVTT0xVVElPTiAzMgogCmNsYXNzIFBvaW50MkQKewpwdWJsaWM6CiAgICBkb3VibGUgeCwgeTsKICAgIAogICAgUG9pbnQyRCgpIHsgeCA9IHkgPSAwLjA7IH07CiAgICBQb2ludDJEKGRvdWJsZSBfeCwgZG91YmxlIF95KSB7IHggPSBfeDsgeSA9IF95OyB9OwogICAgCiAgICBQb2ludDJEIG9wZXJhdG9yICsoY29uc3QgUG9pbnQyRCAmcG9pbnQpIGNvbnN0IHsgcmV0dXJuIFBvaW50MkQoeCArIHBvaW50LngsIHkgKyBwb2ludC55KTsgfTsKICAgIFBvaW50MkQgb3BlcmF0b3IgLShjb25zdCBQb2ludDJEICZwb2ludCkgY29uc3QgeyByZXR1cm4gUG9pbnQyRCh4IC0gcG9pbnQueCwgeSAtIHBvaW50LnkpOyB9OwogICAgUG9pbnQyRCBvcGVyYXRvciAqKGRvdWJsZSB2KSBjb25zdCB7IHJldHVybiBQb2ludDJEKHggKiB2LCB5ICogdik7IH07CiAgICB2b2lkIG9wZXJhdG9yICs9KGNvbnN0IFBvaW50MkQgJnBvaW50KSB7IHggKz0gcG9pbnQueDsgeSArPSBwb2ludC55OyB9OwogICAgdm9pZCBvcGVyYXRvciAtPShjb25zdCBQb2ludDJEICZwb2ludCkgeyB4IC09IHBvaW50Lng7IHkgLT0gcG9pbnQueTsgfTsKICAgIAogICAgdm9pZCBub3JtYWxpemUoKQogICAgewogICAgICAgIGRvdWJsZSBsID0gc3FydCh4ICogeCArIHkgKiB5KTsKICAgICAgICB4IC89IGw7CiAgICAgICAgeSAvPSBsOwogICAgfQp9OwogCmNsYXNzIFNlZ21lbnQKewpwdWJsaWM6CiAgICBQb2ludDJEIHBvaW50c1s0XTsKICAgIAogICAgdm9pZCBjYWxjKGRvdWJsZSB0LCBQb2ludDJEICZwKQogICAgewogICAgICAgIGRvdWJsZSB0MiA9IHQgKiB0OwogICAgICAgIGRvdWJsZSB0MyA9IHQyICogdDsKICAgICAgICBkb3VibGUgbnQgPSAxLjAgLSB0OwogICAgICAgIGRvdWJsZSBudDIgPSBudCAqIG50OwogICAgICAgIGRvdWJsZSBudDMgPSBudDIgKiBudDsKICAgICAgICBwLnggPSBudDMgKiBwb2ludHNbMF0ueCArIDMuMCAqIHQgKiBudDIgKiBwb2ludHNbMV0ueCArIDMuMCAqIHQyICogbnQgKiBwb2ludHNbMl0ueCArIHQzICogcG9pbnRzWzNdLng7CiAgICAgICAgcC55ID0gbnQzICogcG9pbnRzWzBdLnkgKyAzLjAgKiB0ICogbnQyICogcG9pbnRzWzFdLnkgKyAzLjAgKiB0MiAqIG50ICogcG9pbnRzWzJdLnkgKyB0MyAqIHBvaW50c1szXS55OwogICAgfTsKfTsKIApib29sIGNhbGN1bGF0ZVNwbGluZShjb25zdCB2ZWN0b3I8UG9pbnQyRD4gJnZhbHVlcywgdmVjdG9yPFNlZ21lbnQ+ICZiZXppZXIpCnsKICAgIGludCBuID0gdmFsdWVzLnNpemUoKSAtIDE7CiAgICAKICAgIGlmIChuIDwgMikKICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAKICAgIGJlemllci5yZXNpemUobik7CiAgICAKICAgIFBvaW50MkQgdGdMOwogICAgUG9pbnQyRCB0Z1I7CiAgICBQb2ludDJEIGN1cjsKICAgIFBvaW50MkQgbmV4dCA9IHZhbHVlc1sxXSAtIHZhbHVlc1swXTsKICAgIG5leHQubm9ybWFsaXplKCk7CiAgICAKICAgIGRvdWJsZSBsMSwgbDIsIHRtcCwgeDsKICAgIAogICAgLS1uOwogICAgCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG47ICsraSkKICAgIHsKICAgICAgICBiZXppZXJbaV0ucG9pbnRzWzBdID0gYmV6aWVyW2ldLnBvaW50c1sxXSA9IHZhbHVlc1tpXTsKICAgICAgICBiZXppZXJbaV0ucG9pbnRzWzJdID0gYmV6aWVyW2ldLnBvaW50c1szXSA9IHZhbHVlc1tpICsgMV07CiAgICAgICAgCiAgICAgICAgY3VyID0gbmV4dDsKICAgICAgICBuZXh0ID0gdmFsdWVzW2kgKyAyXSAtIHZhbHVlc1tpICsgMV07CiAgICAgICAgbmV4dC5ub3JtYWxpemUoKTsKICAgICAgICAKICAgICAgICB0Z0wgPSB0Z1I7CiAgICAgICAgCiAgICAgICAgdGdSID0gY3VyICsgbmV4dDsKICAgICAgICB0Z1Iubm9ybWFsaXplKCk7CiAgICAgICAgCiAgICAgICAgaWYgKGFicyh2YWx1ZXNbaSArIDFdLnkgLSB2YWx1ZXNbaV0ueSkgPCBFUFNJTE9OKQogICAgICAgIHsKICAgICAgICAgICAgbDEgPSBsMiA9IDAuMDsKICAgICAgICB9CiAgICAgICAgZWxzZQogICAgICAgIHsKICAgICAgICAgICAgdG1wID0gdmFsdWVzW2kgKyAxXS54IC0gdmFsdWVzW2ldLng7CiAgICAgICAgICAgIGwxID0gYWJzKHRnTC54KSA+IEVQU0lMT04gPyB0bXAgLyAoMi4wICogdGdMLngpIDogMS4wOwogICAgICAgICAgICBsMiA9IGFicyh0Z1IueCkgPiBFUFNJTE9OID8gdG1wIC8gKDIuMCAqIHRnUi54KSA6IDEuMDsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgaWYgKGFicyh0Z0wueCkgPiBFUFNJTE9OICYmIGFicyh0Z1IueCkgPiBFUFNJTE9OKQogICAgICAgIHsKICAgICAgICAgICAgdG1wID0gdGdMLnkgLyB0Z0wueCAtIHRnUi55IC8gdGdSLng7CiAgICAgICAgICAgIGlmIChhYnModG1wKSA+IEVQU0lMT04pCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHggPSAodmFsdWVzW2kgKyAxXS55IC0gdGdSLnkgLyB0Z1IueCAqIHZhbHVlc1tpICsgMV0ueCAtIHZhbHVlc1tpXS55ICsgdGdMLnkgLyB0Z0wueCAqIHZhbHVlc1tpXS54KSAvIHRtcDsKICAgICAgICAgICAgICAgIGlmICh4ID4gdmFsdWVzW2ldLnggJiYgeCA8IHZhbHVlc1tpICsgMV0ueCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBpZiAodGdMLnkgPiAwLjApCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBpZiAobDEgPiBsMikKICAgICAgICAgICAgICAgICAgICAgICAgICAgIGwxID0gMC4wOwogICAgICAgICAgICAgICAgICAgICAgICBlbHNlCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBsMiA9IDAuMDsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaWYgKGwxIDwgbDIpCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBsMSA9IDAuMDsKICAgICAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgICAgICAgICAgbDIgPSAwLjA7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIAogICAgICAgIGJlemllcltpXS5wb2ludHNbMV0gKz0gdGdMICogbDE7CiAgICAgICAgYmV6aWVyW2ldLnBvaW50c1syXSAtPSB0Z1IgKiBsMjsKICAgIH0KICAgIAogICAgbDEgPSBhYnModGdMLngpID4gRVBTSUxPTiA/ICh2YWx1ZXNbbiArIDFdLnggLSB2YWx1ZXNbbl0ueCkgLyAoMi4wICogdGdMLngpIDogMS4wOwogICAgCiAgICBiZXppZXJbbl0ucG9pbnRzWzBdID0gYmV6aWVyW25dLnBvaW50c1sxXSA9IHZhbHVlc1tuXTsKICAgIGJlemllcltuXS5wb2ludHNbMl0gPSBiZXppZXJbbl0ucG9pbnRzWzNdID0gdmFsdWVzW24gKyAxXTsKICAgIGJlemllcltuXS5wb2ludHNbMV0gKz0gdGdSICogbDE7CiAgICAKICAgIHJldHVybiB0cnVlOwp9CiAKaW50IG1haW4oKQp7CiAgICB2ZWN0b3I8UG9pbnQyRD4gdGVzdFZhbHVlczsKICAgIHZlY3RvcjxTZWdtZW50PiBzcGxpbmU7CiAgICBQb2ludDJEIHA7CiAKICAgIHRlc3RWYWx1ZXMucHVzaF9iYWNrKFBvaW50MkQoMCwgMCkpOwogICAgdGVzdFZhbHVlcy5wdXNoX2JhY2soUG9pbnQyRCgyMCwgMCkpOwogICAgdGVzdFZhbHVlcy5wdXNoX2JhY2soUG9pbnQyRCg0NSwgLTQ3KSk7CiAgICB0ZXN0VmFsdWVzLnB1c2hfYmFjayhQb2ludDJEKDUzLCAzMzUpKTsKICAgIHRlc3RWYWx1ZXMucHVzaF9iYWNrKFBvaW50MkQoNTcsIDI2KSk7CiAgICB0ZXN0VmFsdWVzLnB1c2hfYmFjayhQb2ludDJEKDYyLCAzODcpKTsKICAgIHRlc3RWYWx1ZXMucHVzaF9iYWNrKFBvaW50MkQoNzQsIDEwNCkpOwogICAgdGVzdFZhbHVlcy5wdXNoX2JhY2soUG9pbnQyRCg4OSwgMCkpOwogICAgdGVzdFZhbHVlcy5wdXNoX2JhY2soUG9pbnQyRCg5NSwgMTAwKSk7CiAgICB0ZXN0VmFsdWVzLnB1c2hfYmFjayhQb2ludDJEKDEwMCwgMCkpOwogCiAgICBjYWxjdWxhdGVTcGxpbmUodGVzdFZhbHVlcywgc3BsaW5lKTsKIAogICAgZm9yIChhdXRvIHMgOiBzcGxpbmUpCiAgICB7CiAgICAgICAgZm9yIChpbnQgaSA9IDA7IGkgPCBSRVNPTFVUSU9OOyArK2kpCiAgICAgICAgewogICAgICAgICAgICBzLmNhbGMoKGRvdWJsZSlpIC8gKGRvdWJsZSlSRVNPTFVUSU9OLCBwKTsKICAgICAgICAgICAgY291dCA8PCBwLnggPDwgIiAiIDw8IHAueSA8PCBlbmRsOwogICAgICAgIH0KICAgIH0KIAogICAgY291dCA8PCB0ZXN0VmFsdWVzLmJhY2soKS54IDw8ICIgIiA8PCB0ZXN0VmFsdWVzLmJhY2soKS55IDw8IGVuZGw7CiAKICAgIHJldHVybiAwOwp9