ZOJ 3728 – Collision [几何]

点击打开zoj题目链接

题意

题目的题意不太好理解,建议多读几遍画画图。就是在一个大圆内有一个小圆形的奖牌,圆心在原点。然后有一个圆形的小硬币,它有一个起始点和一个移动速度,这个硬币碰到奖牌会反弹。问你硬币运动过程中在奖牌内的时间是多少。

分析

硬币是有半径的,可以把硬币看成一个点,然后大圆和奖牌的半径分别分别扩大r。这样就相当于点和两个圆的关系了。求出运动射线和两个圆的交点后,相减除以速度即可。

C++代码

#include <bits/stdc++.h>
using namespace std;

const double eps = 1e-7, inf = 1e9, pi = M_PI;
inline int dcmp(double x) {
    if (fabs(x) < eps) return 0;
    return x < 0 ? -1 : 1;
}
struct Point {
    double x, y;
    Point():x(0), y(0){}
    Point(double x, double y):x(x), y(y){}
    Point(const Point & rhs):x(rhs.x), y(rhs.y){}
    void read() { scanf("%lf%lf", &x, &y); }
    Point operator + (Point rhs) const { return Point(x+rhs.x, y+rhs.y); }
    Point operator - (Point rhs) const { return Point(x-rhs.x, y-rhs.y); }
    Point operator * (double t) const { return Point(x*t, y*t); }
    Point operator / (double t) const { return dcmp(t)==0 ? *this : Point(x/t, y/t); }
    bool operator < (const Point & rhs) const {
        return x < rhs.x || (x == rhs.x && y < rhs.y);
    }
    bool operator == (const Point & rhs) const {
        return !dcmp(x-rhs.x) && !dcmp(y-rhs.y);
    }
    double dot(Point rhs) { return x * rhs.x + y * rhs.y; }
    double cross(Point rhs) { return x * rhs.y - y * rhs.x; }
    double length() { return hypot(x, y); }
    double angle(Point rhs) { return acos(dot(rhs)/length()/rhs.length()); }
    Point rotateAngle(double rad) {
        return Point(x*cos(rad) - y*sin(rad), x*sin(rad) + y*cos(rad));
    }
};
typedef Point Vec;
typedef pair<Point,Point> Line;
typedef vector<Vec> Polygon;

double cross(Vec lhs, Vec rhs) { return lhs.cross(rhs); }
double dot(Vec lhs, Vec rhs) { return lhs.dot(rhs); }

Point getLineInter(Point p, Vec v, Point q, Vec w) {
    Vec u = p - q;
    double t = cross(w, u) / cross(v, w);
    return p + v * t;
}
Point getDotLineProjection(Point P, Point A, Point B) {
    Vec v = B - A;
    return A + v * dot(v, P-A) / dot(v, v);
}
bool inSeg(Point p, Point a1, Point a2) {
    return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) < 0;
}
bool onSeg(Point p, Point a1, Point a2) {
    return dcmp(cross(a1 - p, a2 - p)) == 0 && dcmp(dot(a1 - p, a2 - p)) <= 0;
}
bool segProperInter(Point a1, Point a2, Point b1, Point b2) {
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
    return dcmp(c1 * c2) < 0 && dcmp(c3 * c4) < 0;
}
bool segInter(Point a1, Point a2, Point b1, Point b2) {
    double c1 = cross(a2 - a1, b1 - a1), c2 = cross(a2 - a1, b2 - a1);
    double c3 = cross(b2 - b1, a1 - b1), c4 = cross(b2 - b1, a2 - b1);
    return dcmp(c1 * c2) <= 0 && dcmp(c3 * c4) <= 0;
}
double triArea(Point a, Point b, Point c) {
    return (b-a).cross(c-a)/2.0;
}
double disToLine(Point P, Point A, Point B) {
    Vec v1 = B - A, v2 = P - A;
    return fabs(cross(v1, v2)) / v1.length();
}
double disToSeg(Point P, Point A, Point B) {
    if(A == B) return (P-A).length();
    Vec v1 = B - A, v2 = P - A, v3 = P - B;
    if(dcmp(dot(v1, v2)) < 0) return v2.length();
    if(dcmp(dot(v1, v3)) > 0) return v3.length();
    return fabs(cross(v1, v2)) / v1.length();
}
double circleOverlap(Point c1, double r1, Point c2, double r2) {
    double d = hypot(c1.x-c2.x, c1.y-c2.y);
    if(r1 + r2 < d + eps) return 0;
    if(d < fabs(r1-r2) + eps) {
        double r = min(r1, r2);
        return pi * r * r;
    }
    double x = (d*d + r1*r1 - r2*r2)/(2*d);
    double t1 = acos(x/r1), t2 = acos((d-x)/r2);
    return r1*r1*t1 + r2*r2*t2 - d*r1*sin(t1);
}
double polygonArea(const Polygon & p) {
    double area = 0;
    for (int i = 2; i < p.size(); ++i)
        area += triArea(p[0], p[i - 1], p[i]);
    return area / 2;
}
bool isProtrude(const Polygon & p) {
    Polygon v;
    int sz = p.size();
    for (int i = 0; i < sz; ++i)
        v.push_back(p[(i + 1) % sz] - p[i]);
    int flag = dcmp(cross(v[1], v[0]));
    for (int i = 0; i < sz; ++i)
        if (dcmp(cross(v[(i + 1) % sz], v[i])) != flag)
            return false;
    return true;
}
Polygon convexHull(Polygon p){
    sort(p.begin(), p.end());
    p.erase(unique(p.begin(), p.end()), p.end());
    int i, n = p.size(), m = 0;
    Polygon ch(n + 1);
    for(i = 0; i < n; ++i){
        while(m >= 2 && dcmp(cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) --m;
        ch[m++] = p[i];
    }
    int k = m;
    for(i = n - 2; i >= 0; --i){
        while(m > k && dcmp(cross(ch[m-1]-ch[m-2], p[i]-ch[m-2])) <= 0) --m;
        ch[m++] = p[i];
    }
    if(n > 1) --m; ch.resize(m);
    return ch;
}

//----------------------------------------------------------

struct Circle {
    Point c; double r;
    Circle(Point c, double r): c(c), r(r) {}
    Point getPoint(double a) {
        return Point(c.x + cos(a) * r, c.y + sin(a) * r);
    }
    bool lineInter(Point P, Vec V, Line &res) {
        V = V / V.length();
        Point proj = getDotLineProjection(c, P, P+V);
        double d = disToLine(c, P, P + V);
        if(dcmp(r - d) <= 0) return false;
        d = sqrt(r * r - d * d);
        res.first = proj + V * d, res.second = proj - V * d;
        return true;
    }
};

double Rm, R, r;
Point st; Vec v;


void solve() {
    Circle c1(Point(0, 0), R+r), c2(Point(0, 0), Rm+r);
    Line res1, res2;
    if(!c1.lineInter(st, v, res1)) {
        printf("0.00000\n");
        return;
    }
    if(dcmp(dot(res1.first-st, v)) <= 0 || dcmp(dot(res1.second-st, v)) <= 0) {
        printf("0.00000\n");
        return;
    }
    double lena, lenb;
    lena = (res1.second - res1.first).length();
    if(!c2.lineInter(st, v, res2)) lenb = 0;
    else lenb = (res2.second - res2.first).length();
    printf("%.5f\n", (lena - lenb) / v.length());
}


int main() {
    while(~scanf("%lf%lf%lf", &Rm, &R, &r)) {
        st.read(); v.read();
        solve();
    }
    return 0;
}

欢迎留言