HDU 5572 An Easy Physics Problem-蒲公英云

题目：点击打开链接题意：二维平面中一位于(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;
}