计算几何

向量：

表示：

\(~~~~\)可以表示成\(xi+yj\)，用点对\((x,y)\)代表，结构体存储，模长\(\rho =\sqrt {x^2+y^2}\),幅角\(\theta =\)反$tan\frac y x \(，利用\)cmath\(库函数\)atan2(y,x)\(求得幅角,(表示求\)y\over x\(的反\)tan$)。

运算：

\(1.\)向量与向量的加减运算：两个方向分别进行系数加减。
\(2.\)向量与实数的乘除运算：两个方向分别乘除这个实数。
\(3.\)向量与向量的点积（内积）: 向量\(a\)在另向量\(b\)上的投影（类力的分解）与向量\(b\)的模长的乘积（返回数字）\(|A||B|cos~\theta\)，满足交换律分配率。
\(4.\)向量与向量的叉积（外积）：向量\(a(x_1,y_1)\),向量\(b(x_2,y_2)\),\(a\times b\)表示\((0,0),a,b,a+b\)，四者围成的平行四边形的带符号面积,\(a\times b=x_1y_2-x_2y_1\)（矩阵的行列式）,若\(a\)在\(b\)左面，有向面积为正，反之为负\(|A||B|sin~\theta\)，满足分配率，不满足交换律（交换后答案取反）。
\(5.\)向量放缩：向量\((x,y)/\)原长\(\times\)所需长度。

旋转：

\(~~~~a(x,y)\)可以看成\(x*(1,0),y*(0,1)\)旋转\(\theta\)角变成\(a(x\times cos~\theta-y\times sin~\theta,x\times sin~\theta+y\times cos~\theta)\)

应用：

\(1.\)点积判断角度：小于零为钝角，大于零为锐角，等于零为直角（向量垂直）。
\(2.\)叉积判断方向：
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~a\times b>0 = a\)在\(b\)的顺时针方向
\(~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~a\times b<0 = a\)在\(b\)的逆时针方向
\(~~~~~~~~~~~~~~~~~~~~~~~~~~a\times b=0~=a\)在\(b\)的重合（不一定同向反向）
\(3.\)取出向量的方向：\[\frac{s}{|s|}\]

点、直线、线段的关系：

\(1.\)点到直线距离：叉积得面积除模长求高。
\(2.\)点到线段距离：根据与两端点角度判断高是否在线段上，返回高或与最近端点得距离
\(3.\)判断线段是否相交：从线段一个端点点向另外三个点做差，看线段另一个端点是否被夹在中间，两条线段各做一次。
\(4.\)求两条直线交点：一条直线与另外两点的叉积面积比=高的比=另一条直线被焦点所分的两部分之比。

多边形相关：

\(1.\)求任意多边形面积：选择一点，向其它点做三角剖分，每个三角形的面积和（用叉积求）就是多边形面积。
\(2.\)判断点在多边形内部：选择一点，水平向左引一条射线，若与多边形有奇数个交点，那么点在多边形内部。
\(3.\)求多边形的重心：三角剖分，求每个三角形重心(\(m_i\)表示三角形i的有向面积。)：
\[G_s.x=\frac{\sum m_i\times G_i.x}{\sum m_i}\]
\[G_s.y=\frac{\sum m_i\times G_i.y}{\sum m_i}\]

圆相关：

过一点做切线：求点到圆心距离与半径一起运用反三角函数得角度。
不交圆的外公切线内公切线：做垂直辅助线。

其他算法：

平面凸包：按横坐标排序，正反扫两遍凸壳。
合并凸包：合并两个凸包，就是求出两个凸多边形的桥，用桥把凸包链连起来。求桥用旋转卡壳，从最上方旋转找并踵点，若并踵点两个相邻点（共四个）都在并踵点连线的同一侧，那么这是一个桥。
极角排序：用atan2排，用叉积排（选定基准点（通常是原点）），先排象限再排极角。
坐标系变换：点积求在方向上的距离表示横坐标，叉积求高表示纵坐标，除模长得到高（底）,再除模长是把\(stds\)当成单位向量得到常数。 \[stds=newi-newo,as=a-newo\]
\[P(x,y)=\frac{P(stds\cdot as,stds\times as)}{|stds|^2}\]
旋转卡壳：由于凸包上满足单调性，可以双指针\(O(n)\)扫描，可以求凸包直径/宽度，两凸包的最近最远距离，凸多边形的最小面积/周长外接矩形，合并凸包，凸多边形交\(\cdots\)
半平面交：

注意：

\(1.\)点加减向量为点(移动)，点加减点为向量(产生向量)。
\(2.a\times b=-(b\times a),a\times (-b)=-(a\times b)\)
\(3.\)使用点积叉积判断关系，要把向量平移到原点。
\(4.\)不要求不能确定大体位置的点（误差很大），要用其他方式判定。

三维点积叉积：

点积：数字->投影（相似）->距离。
叉积：向量->方向（法向量）(两向量的叉积方向->同时垂直于两个方向)。
直线平面求交：
平面平面求交：
直线直线求交：
球+平面
球+球
过直线做球的切面
向量围绕向量旋转
三维凸包
SGU 110
UVA11275
POJ1259

他可以做什么：

内公切线、外公切线、放缩直线、求切点切线、多边形面积、维护凸包、最小圆覆盖、求点是否在圆上、旋转卡壳。

#include<iostream>
#include<cmath>
#include<cstring>
#include<cmath>
#include<algorithm>
#define point sector
using namespace std;
struct sector{
    double x,y;
    sector(){x=y=0;}
    double len(){return sqrt(x*x+y*y);}
    double rotate(double x){return (sector){x*cos(a)-y*sin(a),x*sin(a)+y*cos(a)};}//向量旋转（弧度制） 
    sector operator + (const sector &a)const{return (sector){x+a.x,y+a.y};}
    sector operator - (const sector &a)const{return (sector){x-a.x,y-a.y};}
    sector operator * (const double &a)const{return (sector){x*a,y*a};}
    sector operator / (const double &a)const{return (sector){x/a,y/a};} 
}O;
double eps=1e-8;
int dcmp(double x){
    if(fabs(x)<eps) return 0;
    else    return x<0 ? -1:1;
}
bool cmpx(const point &a,const point &b){//按照横坐标排序 
    if(a.x==b.x)    return a.y<b.y;
    return a.x<b.x;
}
bool cmpj1(const point &a,const point &b){//atan2极角排序，快，精度差
    double at1=atan2(a.y,a.x),at2=atan2(b.y,b.x);
    if(at1!=at2)    return at1<at2;
    return a.x<b.x;
}
bool cmpj2(const point &a,const point &b){//叉积极角排序，慢，精度好 
    double at=dcmp(det(a-O,b-O));//以原点作为基准点 
    if(at!=0)   return at>0;
    return a.x<b.x;
}
bool cmpj3(const point &a,const point &b){//先按象限排再按atan2排（雾） 
    if(quad(a)==quad(b))    return a.x<b.x;
    else    return quad(a)<quad(b); 
}
double dot(sector a,sector b){return a.x*b.x+a.y*b.y;}//点积=|a|*|b|*(cos x) 
double det(sector a,sector b){return a.x*b.y-a.y*b.x;}//叉积 
double angle(sector a,sector b){return acos(dot(a,b)/a.len()/b.len());}//上式逆运用求夹角 
double dist_pl(point p,point a,point b){//点到直线距离 
    sector l1=b-a,l2=p-a;
    return fabs(det(l1,l2))/l1.len();
}
double dist_ps(point p,point a,point b){//点到线段的距离 
    if(a==b)    return (p-a).len();
    sector s1=b-a,s2=p-a,s3=p-b;
    if(dcmp(dot(s1,s2))<0)  return s2.len();
    if(dcmp(dot(s1,s3))>0)  return s3.len();
    return fabs(det(s1,s2))/s1.len();
}
double pd_s_in(point a1,point b1,point a2,point b2){//判断线段是否相交 
    double c1=det(a2-a1,b1-a1),d1=det(b2-a1,b1-a1);
    double c2=det(a1-a2,b2-a2),d2=det(b1-a2,b2-a2);
    return dcmp(c1*d1)<0&&dcmp(c2*d2)<0;
}
point find_s_p(point a1,point b1,point a2,point b2){//找线段与线段交点 
    sector l1=b2-a2,l2=b1-a1,l3=a1-a2;
    double ratio=det(l1,l3)/det(l2,l1);
    return a1+l2*ratio;
}
double find_area(point *p,int n){//任意多边形面积，p有序 
    double ans=0;
    for(int i=2;i<n;i++){
        ans+=det(p[i]-p[1],p[i+1]-p[1]);
    }
    return fabs(ans/2);
}
double pd_p_in_s(point a,point *s,int n){//判断点是否在多边形内部 
    int wn=0,k,d1,d2;
    point p1,p2;
    for(int i=1;i<=n;i++){
        p1=s[i];p2=s[(i+1)>n ?i+1-n:i+1];
        if(dcmp(dist_ps(a,p1,p2))==0)   return 1;
        k=dcmp(det(p2-p1,a-p1));
        d1=dcmp(p1.y-a.y);
        d2=dcmp(p2.y-a.y);
        if(k>0&&d1<=0&&d2>0)    wn++;
        if(k<0&&d2<=0&&d1>0)    wn--;
    }
    return wn!=0;
}
point newdkr(point newo,point newi,point a){//建立新的直角坐标系 
    sector stds=newi-newo;
    sector as=a-newo;
    return (point){dot(stds,as),det(stds,as))}/stds.len()/stds.len();
}
void convexhull(point *p,int n,point *coh,int &m){//求凸包 
    m=0;
    sort(p+1,p+1+n,cmpx);
    for(int i=1;i<=n;i++){
        while(m>=2&&dcmp(det(coh[m]-coh[m-1],p[i]-coh[m-1]))<=0)    m--;
        coh[++m]=p[i];
    }
    int k=m;
    for(int i=n-1;i>=1;i--){
        while(m>k&&dcmp(det(coh[m]-coh[m-1],p[i]-coh[m-1]))<=0) m--;
        coh[++m]=p[i];
    }
}
int main(){
    
    return 0;
}

小技巧：

\(1.\)求一个三角形内部有多少点：三角形每条边一侧的点的交/每条边与原点组成的三角形有多少个点容斥一下。
\(2.\)三角形有关：讨论凸包

计算几何

原文：https://www.cnblogs.com/Smeow/p/10582631.html