1 solutions

  • 0
    @ 2025-11-5 14:58:22

    C++ :

    #include <iostream>
    #include <cstdlib>
    #include <cstdio>
    #include <cstring>
    #include <vector>
    #include <cmath>
    #include <algorithm>
     
     
    using namespace std;
     
    const int MAXN = 10000;
    const double PI = atan(1.0) * 4;
    const double EPS = 1e-10;
     
    class Point {
    public:
        double x, y;
        Point() {}
        Point(double x, double y) : x(x), y(y) {}
        Point operator - (const Point &r) const { return Point(x-r.x, y-r.y); }
        Point operator + (const Point &r) const { return Point(x+r.x, y+r.y); }
        Point &operator += (const Point &r) { x += r.x; y += r.y; return *this; }
        Point &operator *= (double m) { x *= m; y *= m; return *this; }
        Point pOfRotate(double angle) const {
            double cosA = cos(angle);
            double sinA = sin(angle);
            return Point(cosA*x-sinA*y, sinA*x+cosA*y);
        }
        Point pOfRotate90() const { return Point(-y, x); }
        double length() const { return sqrt(x*x+y*y); }
        Point pOfNormal() const {
            double len = length();
            return Point(x/len, y/len);
        }
        double angle() const { return atan2(y, x); }
    };
     
    ostream & operator <<(ostream &os, const Point &v)
    {
        os << "(" << v.x << "," << v.y << ")";
        return os;
    }
     
    class Segment;
    class Circle;
     
    class Seg {
    public:
        virtual double getLeft() const = 0;
        virtual double getRight() const = 0;
        virtual double getY(double x) const = 0;
        virtual double getLength(double x1, double x2) const = 0;
        virtual void intersect(Seg *r) const = 0;
        virtual void intersect(const Segment &v) const = 0;
        virtual void intersect(const Circle &v) const = 0;
        bool contains(double x) const { return x>=getLeft() && x<=getRight(); }
        virtual void acceptPrint(ostream &os) const = 0;
    };
     
    ostream & operator <<(ostream &os, const Seg &v)
    {
        v.acceptPrint(os);
        return os;
    }
     
    Point intersectRet[4];
    int tIntersectRet;
     
    class Segment : public Seg {
    public:
        Point a, b;
        Segment &moveLeft(double dis)
        {
            Point tmp = ((b-a).pOfRotate90().pOfNormal() *= dis);
            a += tmp;
            b += tmp;
            return *this;
        }
        virtual double getLeft() const { return a.x; }
        virtual double getRight() const { return b.x; }
        virtual double getY(double x) const {
            return (x-a.x)*(b.y-a.y)/(b.x-a.x)+a.y;
        }
        virtual double getLength(double x1, double x2) const {
            return (x2-x1) * (b-a).length() / (b.x-a.x);
        }
        virtual void intersect(Seg *r) const {
            r->intersect(*this);
        }
        virtual void intersect(const Segment &v) const {
            tIntersectRet = 0;
            double ang = (b-a).angle();
            Point c = (v.a-a).pOfRotate(-ang);
            Point d = (v.b-a).pOfRotate(-ang);
            // Bug
            //double di = b.length();
            double di = (b-a).length();
            if (!((c.y>0&&d.y<0) || (c.y<0&&d.y>0)))
                return ;
            double x = (d.x-c.x) * (-c.y) / (d.y-c.y) + c.x;
            if (x<0 || x>di)
                return ;
            Point ret = Point(x,0).pOfRotate(ang)+a;
            intersectRet[tIntersectRet++] = ret;
        }
        virtual void intersect(const Circle &v) const;
        virtual void acceptPrint(ostream &os) const {
            os << a << "-" << b;
        }
    };
     
    class Circle : public Seg {
    public:
        Point c;
        double r;
        virtual double getLeft() const { return c.x - r; }
        virtual double getRight() const { return c.x + r; }
        virtual double getY(double x) const {
            double y2 = r * r - (c.x - x) * (c.x - x);
            if (y2<0) y2 = 0;
            return c.y + sqrt(y2);
        }
        virtual double getLength(double x1, double x2) const {
            x1 -= c.x; x2 -= c.x;
            double a1 = Point(x1, sqrt(abs(r*r-x1*x1))).angle(), a2 = Point(x2, sqrt(abs(r*r-x2*x2))).angle();
            return (a1-a2) * r;
        }
        virtual void intersect(Seg *r) const {
            r->intersect(*this);
        }
        virtual void intersect(const Segment &v) const {
            tIntersectRet = 0;
            Point a = v.a - c;
            Point b = v.b - c;
            double ang = (b-a).angle();
            Point nA = a.pOfRotate(-ang);
            Point nB = b.pOfRotate(-ang);
            double y = nA.y;
            if (y>r || y<-r)
                return ;
            double x = sqrt(r*r - y*y);
            if (x>=nA.x && x<=nB.x)
                intersectRet[tIntersectRet++] = Point(x, y).pOfRotate(ang) + c;
            if (-x>=nA.x && -x<=nB.x)
                intersectRet[tIntersectRet++] = Point(-x, y).pOfRotate(ang) + c;
        }
        virtual void intersect(const Circle &v) const {
            tIntersectRet = 0;
            Point p = v.c - c;
            double d = p.length();
            if (d > r + v.r || d==0)
                return ;
            double x = (r*r - v.r*v.r + d*d) / (2*d);
            if (x <= r)
            {
                double y = sqrt(abs(r*r - x*x));
                double ang = p.angle();
                intersectRet[tIntersectRet++] = Point(x,y).pOfRotate(ang) + c;
                intersectRet[tIntersectRet++] = Point(x,-y).pOfRotate(ang) + c;
            }
        }
        virtual void acceptPrint(ostream &os) const {
            os << c << "," << r;
        }
    };
     
    void Segment::intersect(const Circle &v) const {
        v.intersect(*this);
    }
     
    int n;
    Point inps[MAXN];
    vector<Seg *> segs;
    vector<double> spes;
    double radius = 1;
     
    void input()
    {
        scanf("%d%lf", &n, &radius);
        for (int i = 0; i < n; ++i)
        {
            double x, y;
            scanf("%lf%lf", &x, &y);
            inps[i] = Point(x, y);
        }
    }
     
    void process()
    {
        segs.clear();
        spes.clear();
        for (int i = 1; i + 1 < n; ++i)
        {
            Circle *tmp = new Circle;
            tmp->c = inps[i];
            tmp->r = radius;
            segs.push_back(tmp);
        }
        for (int i = 0; i + 1 < n; ++i)
        {
            Segment *tmp = new Segment;
            tmp->a = inps[i];
            tmp->b = inps[i+1];
            tmp->moveLeft(radius);
            segs.push_back(tmp);
        }
        for (int i = 0; i < (int)segs.size(); ++i)
        {
            spes.push_back(segs[i]->getLeft());
            spes.push_back(segs[i]->getRight());
        }
        for (int i = 0; i < (int)segs.size(); ++i)
        {
            for (int j = i+1; j < (int)segs.size(); ++j)
            {
                segs[i]->intersect(segs[j]);
                if (tIntersectRet > 0)
                {
                    for (int id = 0; id < tIntersectRet; ++id)
                    {
                        //cout << *segs[i] << " " << *segs[j] << " : " << intersectRet[id] << endl;
                        spes.push_back(intersectRet[id].x);
                    }
                }
            }
        }
        sort(spes.begin(), spes.end());
        double pre = spes[0];
        const double NONE = 1e30;
        double preEnd = NONE;
        double totalLen = 0;
        for (int i = 1; i < (int)spes.size(); ++i)
        {
            if (spes[i]-pre < EPS)
                continue;
            double cur = (pre+spes[i]) / 2;
            //cout << "Processing " << cur << "  from " << pre << " to " << spes[i] << endl;
            if (cur>=inps[0].x && cur<=inps[n-1].x)
            {
                double MY = -NONE;
                int who;
                for (int j = 0; j < (int)segs.size(); ++j)
                {
                    if (!segs[j]->contains(cur))
                        continue;
                    double y = segs[j]->getY(cur);
                    if (y > MY)
                    {
                        MY = y;
                        who = j;
                    }
                }
                if (preEnd != NONE)
                {
                    double LY = segs[who]->getY(pre);
                    //cout << "Drop info " << *segs[who] << " " << "[" << pre << "]" << endl;
                    totalLen += abs(preEnd-LY);
                    //cout << "Pre drop = " << abs(preEnd-LY) << "  from " << preEnd << " to " << LY << endl;
                }
                double len = segs[who]->getLength(pre, spes[i]);
                if (len < 0)
                    printf("Error!\n");
                //cout << "Curlen = " << len << " from " << pre << " to " << spes[i] << endl;
                totalLen += len;
                preEnd = segs[who]->getY(spes[i]);
            }
            pre = spes[i];
        }
        printf("%0.2lf\n", totalLen);
        for (int i = 0; i < (int)segs.size(); ++i)
            delete segs[i];
        segs.clear();
    }
     
    int main()
    {
        input();
        process();
        return 0;
    }
    
    • 1

    Information

    ID
    16282
    Time
    1000ms
    Memory
    128MiB
    Difficulty
    (None)
    Tags
    # Submissions
    0
    Accepted
    0
    Uploaded By