HDU 5572 An Easy Physics Problem

淩亂°似流年 2022-04-15 07:06 166阅读 0赞

## 题目：[点击打开链接][Link 1]   题意：二维平面中一位于(Ax, Ay)的点A以矢量v为方向运动，同时平面内有一半径为r 圆心为Ox Oy的圆，点A碰到圆就会反弹，问运动过程中是否能碰到点B。   分析：这题思路上并不难，写起来比较麻烦，抄的kuangbin的新板子，先判断一下直线AV是否与圆的交点个数，如果少于2个交点，判断B是否在射线AV上，如果有两个交点，求出距离A较近的那个交点P1，求出A关于QP1的对称点A1，判断B是否在线段AP1上或是否在射线P1A1上。 ##

## 补充：这题不用long double也能过，用了保险一点，但是需要调一下eps，不能过大又不能过小，一般在1e-7至1e-8之间。计算几何模板很重要，精度也需要注意，代码比较长，包含注释。   代码： ##

#include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define ld long double
    
    const ld eps = 1e-10;
    const ld inf = 1e20;
    const ld pi = acos(-1.0);
    const int maxp = 1010;
    
    int sgn(ld x){
        if(fabs(x) < eps)return 0;
        if(x < 0)return -1;
        else return 1;
    }
    
    struct Point{
        ld x,y;
        Point(){}
        Point(ld _x,ld _y){
            x = _x;
            y = _y;
        }
        Point operator - (const Point &b)const{
            return Point(x-b.x,y-b.y);
        }
        //叉积
        ld operator ^(const Point &b)const{
            return x*b.y - y*b.x;
        }
        //点积
        ld operator *(const Point &b)const{
            return x*b.x + y*b.y;
        }
        //返回长度
        ld len(){
            return hypot(x,y);//库函数
        }
        //返回长度的平方
        ld len2(){
            return x*x + y*y;
        }
        //返回两点的距离
        ld distance(Point p){
            return hypot(x-p.x,y-p.y);
        }
        Point operator +(const Point &b)const{
            return Point(x+b.x,y+b.y);
        }
        Point operator *(const ld &k)const{
            return Point(x*k,y*k);
        }
        Point operator /(const ld &k)const{
            return Point(x/k,y/k);
        }
        //化为长度为 r 的向量
        Point trunc(ld r){
            ld l = len();
            if(!sgn(l))return *this;
            r /= l;
            return Point(x*r,y*r);
        }
    };
    
    struct Line{
        Point s,e;
        Line(){}
        Line(Point _s,Point _e){
            s = _s;
            e = _e;
        }
        //求线段长度
        ld length(){
            return s.distance(e);
        }
        //返回直线倾斜角 0<=angle<pi
        ld angle(){
            ld k = atan2(e.y-s.y,e.x-s.x);
            if(sgn(k) < 0)k += pi;
            if(sgn(k-pi) == 0)k -= pi;
            return k;
        }
        //点和直线关系
        //1 在左侧
        //2 在右侧
        //3 在直线上
        int relation(Point p){
            int c = sgn((p-s)^(e-s));
            if(c < 0)return 1;
            else if(c > 0)return 2;
            else return 3;
        }
        //点到直线的距离
        ld dispointtoline(Point p){
            return fabs((p-s)^(e-s))/length();
        }
        // 点在线段上的判断
        bool pointonseg(Point p){
            return sgn((p-s)^(e-s)) == 0 && sgn((p-s)*(p-e)) <= 0;
        }
        //返回点 p 在直线上的投影
        Point lineprog(Point p){
            return s + ( ((e-s)*((e-s)*(p-s)))/((e-s).len2()) );
        }
        //返回点 p 关于直线的对称点
        Point symmetrypoint(Point p){
            Point q = lineprog(p);
            return Point(2*q.x-p.x,2*q.y-p.y);
        }
    };
    
    struct circle{
        Point p;//圆心
        ld r;//半径
        circle(Point _p,ld _r){
            p = _p;
            r = _r;
        }
        //直线和圆的关系
        //比较的是圆心到直线的距离和半径的关系
        int relationline(Line v){
            ld 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);
            ld 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;
        }
    };
    
    int t,r;
    Point Q,A,B,V;
    int main() {
        cin>>t;
        for(int cas=1;cas<=t;cas++) {
            cin>>Q.x>>Q.y>>r;
            cin>>A.x>>A.y>>V.x>>V.y;
            cin>>B.x>>B.y;
            V=Point(A.x+V.x,A.y+V.y);
            Line LA=Line(A,V);
            circle O = circle(Q,r);
            Point P1,P2;
            int cnt = O.pointcrossline(LA,P1,P2);
            int f=0;
            if(cnt==0||cnt==1) {
                ///如果圆和向量(直线)AV少于两个交点，直接判断点B是否在射线AV上
                if(LA.relation(B) == 3 && sgn((V-A)*(B-A)) > 0 ) f=1;
            }else {
                ///否则先判断点B是否在线段AP1上，再判断是否在射线P1A1上，A1为点A关于直线QP1(圆的半径)的对称点
                if(sgn(A.distance(P1)-A.distance(P2)) >0 ) P1=P2;///P1为第一个交点(较近的点)
                Line QP1=Line(Q,P1);
                Line AP1=Line(A,P1);
                Point A1=QP1.symmetrypoint(A);
                if( AP1.pointonseg(B)) f=1;
                Line P1A1=Line(P1,A1);
                if( P1A1.relation(B) == 3 && sgn((A1-P1)*(B-P1)) > 0 ) f=1;
            }
            cout<<"Case #"<<cas<<": ";
            if(f) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }
        return 0;
    }

[Link 1]: http://acm.hdu.edu.cn/showproblem.php?pid=5572