HDU - 5572 An Easy Physics Problem （计算几何模板）

#include <algorithm>
#include <cstdio>
#include <vector>
#include <cmath>
using namespace std;

const double eps = 1e-8; //1e-10会WA，注意调整精度，过大过小都不行

//浮点数是否等于0，在eps精度范围之内 
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(double x=0,double y=0):x(x),y(y){}
    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 length(Vector A){ return mySqrt(dot(A,A));}
//叉积定义 
double cross(Vector A,Vector B){ return A.x * B.y - A.y * B.x;}

//直线结构体 
struct Line
{
    //相当于点向式 
    //   (x - x0) / v.x =  (y - y0) / v.y 
    Point p;//直线上一点 
    Vector v;//方向向量定方向 
    Line(Point p,Vector v):p(p),v(v){}
    Point getPoint(double t){ 
        return Point(p.x + v.x*t,p.y + v.y*t);
    }
};

//圆的结构体定义 圆心和半径即可 
struct Circle
{
    Point c;
    double r;
    Circle(Point c,double r):c(c),r(r){}
};

//求圆和直线交点 ，返回1有两个实数解，其他返回0
int getLineCircleIntersection(Line L,Circle C,Point& P){ //返回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 f = 2*(a*b + c*d);
    double g = b*b + d*d - C.r*C.r;

    double delta = f*f - 4*e*g;
    
    //判别式大于0 一元二次方程才有实数解 
    if(dcmp(delta) <= 0) return 0;
    //一元二次方程求根公式 
    double t = (-f - mySqrt(delta)) / (2*e);
    
    P = L.getPoint(t);
    return 1;
}

int getLineCircleIntersection2(Line L,Point& P,Point& Q){ //返回两个点
    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 f = 2*(a*b + c*d);
    double g = b*b + d*d - C.r*C.r;

    double delta = f*f - 4*e*g;
    
    //判别式大于0 一元二次方程才有两个实数解 
    if(dcmp(delta) < 0) return 0;
    //一元二次方程求根公式 
    double t1 = (-f - mySqrt(delta)) / (2*e);
    double t2 = (-f + mySqrt(delta)) / (2*e);
    P = L.getPoint(t1);
    Q = L.getPoint(t2);
    return 1;
}
//点是否在直线上 
bool onLine(Point A,Line L){
    Vector w = A - L.p;    
    //printf("%lf %lfn",w.x,w.y);
    //叉积为0即共线 
    if(dcmp(cross(w,L.v)) == 0)
        return true;
    else return false;
}

bool onRay(Point A,Line L){//点A在射线L(p,v)上，不含端点
    Vector w = A - L.p;
    //叉积等于0且点乘大于0 
    if(dcmp(cross(w,L.v))==0 && dcmp(dot(w,L.v)) > 0) return true;
    return false;
}

bool onSeg(Point A,Point B,Point C){//点A在线段BC上
    //叉积等于0且点乘小于0 
    return dcmp(cross(B-A,C-A))==0 && dcmp(dot(B-A,C-A))<0;
}

Point project(Point A,Line L){
    return L.p + L.v * ( dot(L.v,A - L.p) / dot(L.v,L.v) );
}

//求点A关于直线L的对称点 
Point mirrorPoint(Point A,Line L){
    Vector D = project(A,L);
    //printf("project: %lf,%lfn",D.x,D.y);
    return D + (D - A);
}

int main()
{
    int T;
    int ans = 0;
    double R;
    Point O,A,B;
    Vector V;
    /*
    A = Point(1,0);
    V = Point(1,1);
    Line L1 =  Line(A,V);
    
    O.x = 2;
    O.y = 0;
    
    Circle yuanO = Circle(O,1);
    int tt = getLineCircleIntersection2( L1,yuanO,B);
    printf("%lf %lfn",A.x,A.y);
    printf("%lf %lfn",B.x,B.y);
    */
   /* A = Point(1,1);
    Line l1 =  Line(A,V);
    printf("%lf %lf %lf %lfn",l1.p.x,l1.p.y,l1.v.x,l1.v.y);
    B = Point();
    while(scanf("%lf%lf",&B.x,&B.y) != EOF){
        printf("%lf %lfn",B.y);
        printf("%dn",onLine( B,l1));
    }*/
    
    
    
    scanf("%d",&T);
    for(int ca = 1; ca <= T; ca++){
        
        scanf("%lf%lf%lf",&O.x,&O.y,&R);
        scanf("%lf%lf%lf%lf",&A.x,&A.y,&V.x,&V.y);
        scanf("%lf%lf",&B.y);
        
        Line LA = Line(A,V);
        Circle yuanO = Circle(O,R);
        Point C;
        
        if(getLineCircleIntersection(LA,C)){
            if(onSeg(B,C)) ans = 1;
            else{
                //直线OC是对称轴 
                Line OC = Line(O,Vector(C.x - O.x,C.y - O.y));
                Point A1 = mirrorPoint(A,OC);
                // printf("%lf,C.x,C.y);
                // printf("%lf,A1.x,A1.y);
                
                //射线CB 
                Line CB = Line(C,Vector(B.x - C.x,B.y - C.y));
                
                if(onRay(A1,CB)){
                     ans = 1;

                }
                else ans = 0;
            }
        }else{
            if(onRay(B,LA)) ans = 1;
            else ans = 0;
        }
        printf("Case #%d: %sn",ca,ans ? "Yes" : "No");
    }

    return 0;
}