1 条题解

  • 0
    @ 2025-5-27 15:37:55
    #include <iostream>
    #include <vector>
    #include <cmath>
    #include <iomanip>
    #include <string>
    
    using namespace std;
    
    struct Point {
        double x, y;
        Point() {}
        Point(double xx, double yy): x(xx), y(yy) {}
    };
    
    double cross(const Point& o, const Point& a, const Point& b) {
        return (a.x - o.x)*(b.y - o.y) - (a.y - o.y)*(b.x - o.x);
    }
    
    bool isConvex(const vector<Point>& poly) {
        int n = poly.size();
        if (n < 3) return false;
        bool first = true, pos = false;
        for (int i = 0; i < n; ++i) {
            double cp = cross(poly[i], poly[(i+1)%n], poly[(i+2)%n]);
            if (cp != 0) {
                if (first) {
                    pos = cp > 0;
                    first = false;
                } else if ((cp > 0) != pos) {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool pointInPolygon(const Point& p, const vector<Point>& poly) {
        int n = poly.size();
        bool inside = false;
        for (int i = 0; i < n; ++i) {
            Point a = poly[i], b = poly[(i+1)%n];
            if ((a.y > p.y) != (b.y > p.y)) {
                double xint = (b.x - a.x) * (p.y - a.y) / (b.y - a.y + 1e-10) + a.x;
                if (p.x < xint)
                    inside = !inside;
            }
        }
        return inside;
    }
    
    double distToSegment(Point p, Point a, Point b) {
        double dx = b.x - a.x, dy = b.y - a.y;
        if (dx == 0 && dy == 0)
            return hypot(p.x - a.x, p.y - a.y);
        double t = ((p.x - a.x) * dx + (p.y - a.y) * dy) / (dx*dx + dy*dy);
        t = max(0.0, min(1.0, t));
        double projx = a.x + t * dx;
        double projy = a.y + t * dy;
        return hypot(p.x - projx, p.y - projy);
    }
    
    bool pegFits(const vector<Point>& poly, const Point& peg, double radius) {
        if (!pointInPolygon(peg, poly)) return false;
        int n = poly.size();
        for (int i = 0; i < n; ++i) {
            Point a = poly[i], b = poly[(i+1)%n];
            double d = distToSegment(peg, a, b);
            if (d < radius - 1e-8)
                return false;
        }
        return true;
    }
    
    int main() {
        cout << fixed << setprecision(2);
        int n;
        while (cin >> n) {
            if (n < 3) break;
            double radius, px, py;
            cin >> radius >> px >> py;
            vector<Point> poly;
            for (int i = 0; i < n; ++i) {
                double x, y;
                cin >> x >> y;
                poly.push_back(Point(x, y));
            }
    
            if (!isConvex(poly)) {
                cout << "HOLE IS ILL-FORMED" << endl;
            } else if (pegFits(poly, Point(px, py), radius)) {
                cout << "PEG WILL FIT" << endl;
            } else {
                cout << "PEG WILL NOT FIT" << endl;
            }
        }
        return 0;
    }
    • 1

    信息

    ID
    585
    时间
    1000ms
    内存
    10MiB
    难度
    9
    标签
    递交数
    2
    已通过
    1
    上传者