HDU5572 2015ICPC上海A计算几何

HDU5572 2015ICPC上海A计算几何 题目

HDU 5572

无限大的平面上，有一个圆柱。圆柱外有两个点A、B，点A有个速度向量V，A撞到圆柱会发生完全d性碰撞。问点A是否能经过点B。

解题思路

我们记A -> A+V的运动轨迹为直线 l 1 l1 l1（射线在代码实现中并不好处理）。
共分以下几种情况：

一、 l 1 l1 l1与圆不相交
判断A是否能直接经过B，即判断向量 V ⃗ 、 B − A ⃗ vec{V}、vec{B-A} V 、B−A ​是否同向。

二、 l 1 l1 l1与圆相切
情况同一。

三、 l 1 l1 l1与圆相交
记 l 1 l1 l1与圆距离较近的点为X。

1. 判断是否是正向相交，即判断向量 V ⃗ 、 X 1 − A ⃗ vec{V}、vec{X1-A} V 、X1−A ​是否同向。如果不是，那么回到条件一。否则继续判断。
2. 记圆心与X确定的直线为 l 2 l2 l2，并记A关于直线 l 2 l2 l2的对称点为 A 2 A_2 A2​，则A和圆柱碰撞后会延 X A 2 XA_2 XA2​运动。在这个过程中，有以下几种经过B的可能：①点B在线段AX上。②点B在XA的延长线上。

代码

#include 
using namespace std;

const double eps = 1e-5;
int sgn(double x)
{
    if (fabs(x) < eps)
        return 0;
    if (x < 0)
        return -1;
    return 1;
}
typedef struct Point
{
    double x, y;
    Point(){};
    Point(double _x, double _y) { x = _x, y = _y; }
    Point operator*(const double &b) const { return Point{x * b, y * b}; }
    Point operator/(const double &b) const { return Point{x / b, y / b}; }
    Point operator-(const Point &b) const { return Point{x - b.x, y - b.y}; }
    Point operator+(const Point &b) const { return Point{x + b.x, y + b.y}; }
    double operator^(const Point &b) const { return x * b.y - y * b.x; }
    double operator*(const Point &b) const { return x * b.x + y * b.y; }
    bool operator==(const Point &b) const { return sgn(x - b.x) == 0 && sgn(y - b.y == 0); }
    double distance(Point p) { return hypot(x - p.x, y - p.y); }
    double len() { return hypot(x, y); }
    double len2() { return x * x + y * y; }
    Point trunc(double r)
    {
        double l = len();
        if (!sgn(l))
            return *this;
        r /= l;
        return Point(x * r, y * r);
    }
} Vector;
struct Line
{
    Point s, e;
    Line(){};
    Line(Point _s, Point _e) { s = _s, e = _e; }

    double length()
    {
        return s.distance(e);
    }
    Point lineprog(Point p)
    {
        return s + (((e - s) * ((e - s) * (p - s))) / ((e - s).len2()));
    }
    double dispointtoline(Point p)
    {
        return fabs((p - s) ^ (e - s)) / length();
    }
    Point symmetrypoint(Point p)
    {
        Point q = lineprog(p);
        return Point(2 * q.x - p.x, 2 * q.y - p.y);
    }
    // 点在线段上的判断
    bool pointonseg(Point p)
    {
        return sgn((p - s) ^ (e - s)) == 0 && sgn((p - s) * (p - e)) <= 0;
    }
};
struct Circle
{
    Point p;
    double r;
    Circle(){};
    Circle(Point _p, double _r) { p = _p, r = _r; }
    int relationline(Line v)
    {
        double dst = v.dispointtoline(p);
        if (sgn(dst - r) < 0)
            return 2;
        else if (sgn(dst - r) == 0)
            return 1;
        return 0;
    }
    int pointcrossline(Line v, Point &p1, Point &p2)
    {
        if (!(*this).relationline(v))
            return 0;
        Point a = v.lineprog(p);
        double d = v.dispointtoline(p);
        d = sqrt(r * r - d * d);
        if (sgn(d) == 0)
        {
            p1 = a;
            p2 = a;
            return 1;
        }
        p1 = a + (v.e - v.s).trunc(d);
        p2 = a - (v.e - v.s).trunc(d);
        return 2;
    }
};

bool check(Vector a, Vector b) //向量同向
{
    return sgn(atan2(a.y, a.x) - atan2(b.y, b.x)) == 0;
}
int CA;

void solve()
{
    double r;
    Point O, A, B;
    Vector V;
    scanf("%lf %lf %lf %lf %lf %lf %lf %lf %lf", &O.x, &O.y, &r, &A.x, &A.y, &V.x, &V.y, &B.x, &B.y);
    if (sgn(O.distance(A) - r) <= 0 || sgn(O.distance(B) - r) <= 0)
        while (1)
            puts("1");
    Circle cir(Point{O.x, O.y}, r);
    Line l1(A, A + V);
    if (cir.relationline(l1) <= 1)
    {
        if (check(V, B - A))
            printf("Case #%d: Yesn", ++CA);
        else
            printf("Case #%d: Non", ++CA);
        return;
    }
    Point X1, X2;
    cir.pointcrossline(l1, X1, X2);
    if (!check(V, X1 - A))
    {
        if (check(V, B - A))
            printf("Case #%d: Yesn", ++CA);
        else
            printf("Case #%d: Non", ++CA);
        return;
    }
    if (X1.distance(A) > X2.distance(A))
        swap(X1, X2);
    Line l3(X1, A);
    if (l3.pointonseg(B))
    {
        printf("Case #%d: Yesn", ++CA);
        return;
    }
    Line l2(O, X1);
    Point Y = l2.symmetrypoint(B);
    if (check(Y - X1, A - X1))
    {
        printf("Case #%d: Yesn", ++CA);
        return;
    }
    printf("Case #%d: Non", ++CA);
}

int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
    return 0;
}