1 条题解
-
0
#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
- 上传者