向量:
表示:
\(~~~~\)可以表示成 \(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.\)三角形有关: 讨论凸包
计算几何
来源: http://www.bubuko.com/infodetail-2996633.html