A Round Peg in a Ground Hole

题目链接

[POJ 1584] A Round Peg in a Ground Hole

题解

中档题。题意大概是给定一组多边形,首先判断其是不是凸多边形,其次判断给定圆的圆心是否在多边形内,最后判断圆心到所有边的距离是否大于给定的半径。

代码

#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;

const double eps = 1e-10;
int n;
double r;
struct Point {
    double x, y;
} dimp;
vector<Point>vec;

inline int flag(double x) {
    return x > eps ? 1 : (x < -eps ? 2 : 0);
}

double Cross(Point p1, Point p2, Point p0) {
    return (p1.x - p0.x)*(p2.y - p0.y) - (p2.x - p0.x)*(p1.y - p0.y);
}

bool isConvex() {
    int i, s[3] = { 1,1,1 };
    for (i = 0; i<n&&s[1] | s[2]; i++) {
        s[flag(Cross(vec[(i + 1) % n], vec[(i + 2) % n], vec[i]))] = 0;
    }
    return s[1] | s[2];
}

int isInside(Point q) {
    int i, s[3] = { 1,1,1 };
    for (i = 0; i<n&&s[1] | s[2]; i++) {
        s[flag(Cross(vec[(i + 1) % n], q, vec[i]))] = 0;
    }
    return s[0] && (s[1] | s[2]);
}

double dis(Point a, Point b) {
    return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));
}

Point inter(Point u1, Point u2, Point v1, Point v2) {
    Point ret = u1;
    double t = ((u1.x - v1.x)*(v1.y - v2.y) - (u1.y - v1.y)*(v1.x - v2.x))
        / ((u1.x - u2.x)*(v1.y - v2.y) - (u1.y - u2.y)*(v1.x - v2.x));
    ret.x += (u2.x - u1.x)*t;
    ret.y += (u2.y - u1.y)*t;
    return ret;
}

Point lineCross(Point p, Point l1, Point l2) {
    Point t = p;
    t.x += l1.y - l2.y;
    t.y += l2.x - l1.x;
    if (Cross(l1, t, p)*Cross(l2, t, p)>eps)
        return dis(p, l1)<dis(p, l2) ? l1 : l2;
    return inter(p, t, l1, l2);
}

int main() {
    while (cin >> n) {
        if (n<3)break;
        vec.clear();
        cin >> r >> dimp.x >> dimp.y;
        Point input;
        for (int i = 0; i<n; i++) {
            cin >> input.x >> input.y;
            vec.push_back(input);
        }
        if (!isConvex()) {
            cout << "HOLE IS ILL-FORMED" << endl;
            continue;
        }
        if (!isInside(dimp)) {
            cout << "PEG WILL NOT FIT" << endl;
            continue;
        }
        bool temp(false);
        for (int i = 0; i<n; i++) {
            input = lineCross(dimp, vec[i], vec[(i + 1) % n]);
            double dist = dis(input, dimp);
            if (dist<r) {
                temp = true;
                break;
            }
        }
        if (temp)cout << "PEG WILL NOT FIT" << endl;
        else  cout << "PEG WILL FIT" << endl;
    }
    return 0;
}

标签: math, geometry

添加新评论