计算几何全家桶-526互联

一、准备工作

#define LD double
#define Vector Point
#define Re register int 
const LP eps=1e-8;//据说：出题的大学生基本上用的这个值
inline int dcmp(LD a){ return a<eps?-1:(a>eps?1:0); }
inline LD Abs(LD a){ return a*dcmp(a); }//绝对值
struct Point{
    LD x,y;Point(LD X=0,LD Y=0){ x=X,y=Y; }
    inline void in(){ cin>>x>>y; }
    inline void out(){ printf("%.2lf %.2lf\n",x,y); }
};

二、向量

1.模长

对于 $\vec{a}=(x,y), \left | \vec{a} \right |=\sqrt{x^{2}+y^{2}}=\sqrt{\left | \vec{a} \right |^{2}}=\sqrt{\vec{a}\cdot \vec{a}}$

inline LD len(Vector a){ return sqrt(Dot(a,a)); }

2.向量加减

inline Vector operator+(Vector a,Vector b){ return Vector(a.x+b.x,a.y+b.y);}
inline Vector operator- (Vector a,Vector b){ return Vector(a.x -b.x,a.y -b.y); }

3.向量数乘

对于 $\vec{a}=(x,y),\lambda \vec{a}=(\lambda x,\lambda y)$

除法也可以理解为数乘： $\frac{\vec{a}}{\lambda }=\frac{1}{\lambda }\vec{a}=(\frac{1}{\lambda }x,\frac{1}{\lambda }y)$

inline Vector operator* (Vector a,LD b){ return Vector(a.x*b,a.y*b); }

4.点积（内积）（数量积）

inline LD Dot(Vector a,Vector b){ return a.x*b.x+a.y*b.y; }

5.叉积（外积）（向量积）

inline LD Cro(Vector a,Vector b){ return a.x*b.y -a.y*b.x; }

三、点，向量的位置变换

1.点、向量的旋转

(1).对于点 P=(x,y) 或向量 $\vec{a}=(x,y)$ ，将其顺时针旋转 $\begin{vmatrix} x & y \end{vmatrix} \times \begin{vmatrix} cos\theta &-sin\theta \\ sin\theta & cos\theta \end{vmatrix}=\begin{vmatrix} xcos\theta +ysin\theta & -xsin\theta +ycos\theta \end{vmatrix}$

inline Point turn_P(Point a,LD theta){
    LD x=a.x*cos(theta)+a.y*sin(theta);
    LD y=-a.x*sin(theta)+a.y*cos(theta);
    return Point(x,y);
}

(2).将点A(x,y)绕点B(x₀,y₀)顺时针旋转θ角度：

$\begin{vmatrix} (x-x_{0})cos\theta +(y-y_{0})sin\theta+x_{0} & -(x-x_{0})sin\theta +(y-y_{0})cos\theta +y_{0} \end{vmatrix}$

inline Point turn_PP(Point a,Point b,LD theta){
    LD x=(a.x-b.x)*cos(theta)+(a.y-b.y)*sin(theta)+b.x;
    LD y=-(a.x-b.x)*sin(theta)+(a.y-b.y)*cos(theta)+b.y;
    return Point(x,y);
}

四、图形与图形之间的关系

1.点与线段

(1).判断点P是否在线段AB上：

inline int pan_PL(Point p,Point a,Point b){
    return !dcmp(Cro(p-a,b-a))&&dcmp(Dot(p-a,p-b))<=0;
}

(2).点P到线段AB的距离：

inline bool operator==(Point a,Point b){ return !dcmp(a.x-b.x)&&!dcmp(a.y-b.y); }//两点重合则坐标相等
inline LD dis_PL(Point p,Point a,Point b){
    if(a==b) return Len(p-a);
    Vector x=p-a,y=p-b,z=b-a;
    if(dcmp(Dot(x,z))<0) return Len(x);//P距离A更近
    if(dcmp(Dot(y,z))<0) return Len(y);//P距离B更近
    return Abs(Cro(x,z)/Len(z));//面积除以底边长
}

2.点与直线

(1).判断点P是否在直线AB上：

inline int pan_PL_(Point p,Point a,Point b){//判断点P是否在直线AB上
    return !dcmp(Cro(p-a,b-a));
}

(2).点P到直线AB的垂足F：

inline Point FootPoint(Point p,Point a,Point b){//点P到直线AB的垂足
    Vector x=p-a,y=p-b,z=b-a;
    LD len1=Dot(x,z)/Len(z),len2=-1.0*Dot(y,z)/Len(z);//分别计算AP,BP在AB,BA上的投影
    return a+z*(len1/(len1+len2));//点A加上向量AF
}

(3).点P关于直线AB的对称点：

inline Point Symmetry_PL(Point p,Point a,Point b){//点P关于直线AB的对称点
    return p+(FootPoint(p,a,b)-p)*2;//将PF延迟一倍即可
}