ICPC 7400 / HDU 5572 An Easy Physics Problem

acm geometric

參考 http://www.cnblogs.com/helenawang/p/5465481.html
再加上一些註解

復習了一下 cross product 和 dot product
在這記錄一下如何找 line segment 和 circle 的 intersection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let we have Point A and B
We know the center of circle C and it radius

We set Point P which is between AB, angle CPA = 90 // 事實上OP 和 AB不是連起來也可以
let ( x(vector AB) + (vector CA) ) . (vector AB) = 0
since we know AB, CA. we can find x

x(vector AB) = (vector AP)

Then we can find x, y of P

radius^2 - CP^2 = QP ^ 2 // Q is the first intersection

Lastly we can use the ratio to get location of Q
hdu5572.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const double eps = 1e-8;

int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}

double mySqrt(double x) {
    return sqrt(max((double)0, x));
}


struct Point {
    double x, y;
    Point() {}
    Point(double a, double b): x(a), y(b) {}
    Point& operator = (Point p) {
        x = p.x;
        y = p.y;
        return *this;
    }
};
typedef Point Vector;
Vector operator + (Vector a, Vector b) { return Vector(a.x + b.x, a.y + b.y); }
Vector operator - (Point a, Point b) { return Vector(a.x - b.x, a.y - b.y); }
Vector operator * (Vector a, double p) { return Vector(a.x * p, a.y * p); }
Vector operator / (Vector a, double p) { return Vector(a.x / p, a.y / p); }

double dot(Vector a, Vector b) { return a.x*b.x + a.y*b.y; }
double cross(Vector a, Vector b) { return a.x*b.y - a.y*b.x; }

struct Line {
    Point p;
    Vector v;
    Line(Point p, Vector v) : p(p), v(v) {}
    Point getPoint(double t) {
        return Point(p.x + t*v.x, p.y + t*v.y);
    }
};

struct Circle {
    Point c;
    double r;
    Circle(Point c, double r) : c(c), r(r) {}
};

double dists(Point p1, Point p2) {
    return sqrt((p1.x - p2.x)*(p1.x - p2.x) + (p1.y - p2.y)*(p1.y - p2.y));
}
// Here b is the the b in question, is the line AB intersect circle
// assume ab is 1
// t*(ABx^2 + ABy^2) - (ABx*CAx + ABy*CAy) = 0
// let ABx = a, ABy = c, CAx = b, CAy = d;
int getLineCircleIntersection(Line L, Circle C, Point& Q) { //返回t较小的那个点
    double a = L.v.x;
    double b = L.p.x - C.c.x;
    double c = L.v.y;
    double d = L.p.y - C.c.y;

    double e = a*a + c*c;
    double t = (-1 * (a*b + c*d)) / e;
    Point p = L.getPoint(t);

    double cp = dists(p, C.c);
    if (cp > C.r) return 0;
    double qp = sqrt(C.r*C.r - cp*cp);

    double ap = dists(p, L.p);

    double ratio = (ap - qp) / ap;
    Q = L.getPoint(t*ratio);

    return true;
}

// A in Line L
bool onRay(Point A, Line L) {
    Vector LA = A - L.p;
    // sin 0 = 0, cos 0 = 1
    return dcmp(cross(LA, L.v)) == 0 && dcmp(dot(LA, L.v)) > 0;;
}


// A in BC
bool onSegment(Point A, Point B, Point C) {
    // sin 180 = 0, cos 180 = -1
    return dcmp(cross(B - A, C - A)) == 0 && dcmp(dot(B - C, C - A)) < 0;
}


// the mid point between A and D
Point mirrorVec(Point A, Line L) {
    // |lv| |AO| cosx / |lv| |lv| 1 = OC / |lv|
    // (ga)^2 + (gb)^2 = (gc)^2, ratio in length change can be used in ratio in x, y change
    double ratioOC2OD = dot(L.v, A - L.p)/dot(L.v, L.v);
    return L.p + L.v * ratioOC2OD;
}

Point mirrorPoint(Point A, Line L) {
    Vector D = mirrorVec(A, L);
    return D + (D - A);
}


Point O, A, B, Q;
Vector V;
double radius;

bool canTouch() {
    Circle C(O, radius);
    Line LA(A, V);
    if (getLineCircleIntersection(LA, C, Q)) {
        if (onSegment(B, A, Q)) return true;

        Line CQ(O, Q - C.c);
        Point mA = mirrorPoint(A, CQ);

        Line QB(Q, B - Q);
        if(onRay(mA, QB)) {
            return true;
        }
    }
    else {
        if (onRay(B, LA)) return true;
    }
    return false;
}

int main() {
    // freopen("input.txt", "r", stdin);

    int T;
    scanf("%d", &T);
    for (int tcase = 1; tcase <= T; ++tcase) {
        scanf("%lf%lf%lf", &O.x, &O.y, &radius);
        scanf("%lf%lf%lf%lf", &A.x, &A.y, &V.x, &V.y);
        scanf("%lf%lf", &B.x, &B.y);

        if (!canTouch()) {
         printf("Case #%d: No\n", tcase);
        }
        else {
         printf("Case #%d: Yes\n", tcase);
        }
    }

    return 0;
}