叉乘，向量是否有交点，点在线的哪侧.cpp

acm中各种代码

#include<stdio.h> 
//计算几何模板 ~ alpc02
const double PRECISION = 1e-8;
struct Point {
   double x, y;
5};
6int dblcmp(double d) {
7    return (fabs(d) < PRECISION) ? 0:(d>0 ? 1:-1);
8} //三叉口函数，避免精度误差
9double length(double x, double y) {
10    return sqrt(x*x + y*y);
11} //向量长度

double dotdet(double x1, double y1, double x2, double y2) {
    return x1*x2 + y1*y2;
} //点积，AB * CD = |AB| * |CD| * cos(a) 
double det(double x1, double y1, double x2, double y2) {
    return x1*y2 - x2*y1;
} //叉积，AB×CD = |AB| * |CD| * sin(a) 
int cross(const Point &a, const Point &c, const Point &d) {
    return dblcmp( det(a.x-c.x, a.y-c.y, d.x-c.x, d.y-c.y) );
} //右手螺旋定则，1——a在cd右侧，-1——a在cd左侧，0——三点共线；逆时针为正方向 
bool between(const Point &a, const Point &c, const Point &d) {
    return dblcmp( dotdet(c.x-a.x, c.y-a.y, d.x-a.x, d.y-a.y) ) != 1;
} //在cross(a,c,d)==0的基础上，可判断点a是否在cd内部
int segIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
    int a_cd = cross(a,c,d);
    if(a_cd == 0 && between(a,c,d))    return 2;
    int b_cd = cross(b,c,d);
    if(b_cd == 0 && between(b,c,d))    return 2;
    int c_ab = cross(c,a,b);
    if(c_ab == 0 && between(c,a,b))    return 2;
    int d_ab = cross(d,a,b);
    if(d_ab == 0 && between(d,a,b))    return 2;
    if ((a_cd ^ b_cd) == -2 && (c_ab ^ d_ab) == -2)
        return 1;
    return 0;
} //两线段相交情况：0——不相交，1——规范相交，2——不规范相交（交于端点或重合）
void intersectPoint(const Point &a, const Point &b, const Point &c, const Point &d, Point &e) {
    double sc, sd;
     sc = fabs( det(b.x-a.x, b.y-a.y, c.x-a.x, c.y-a.y) );
     sd = fabs( det(b.x-a.x, b.y-a.y, d.x-a.x, d.y-a.y) );
     e.x = (sc * d.x + sd * c.x) / (sc + sd);
     e.y = (sc * d.y + sd * c.y) / (sc + sd);
} //两线段规范相交时，求交点坐标
int linesegIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {
    int c_ab = cross(c,a,b);
    if(c_ab == 0)    return 2;
    int d_ab = cross(d,a,b);
    if(d_ab == 0)    return 2;
    if(c_ab ^ d_ab == -2)
        return 1;
    return 0;
} //直线ab和线段cd相交情况：0——不相交，1——规范相交，2——不规范相交（交于端点或重合）
int lineIntersect(const Point &a, const Point &b, const Point &c, const Point &d) {

    if(dblcmp(det(b.x-a.x, b.y-a.y, d.x-c.x, d.y-c.y)) != 0)
        return 1;
    if(cross(a,c,d) == 0)
        return 2;
    return 0;
} //两直线相交情况：0——平行，1——规范相交，2——不规范相交（重合）