一, 矢量
1. 定义: 是一条有方向的线段的长度
如图,\(a\)就是线段 \(\overrightarrow{AB}\)的矢量
2. 三角形法则
如图
- \(\because \overrightarrow{
- AB
- }\)\(=a\),\(\overrightarrow{
- BC
- }\)\(=b\)
- \(\therefore \overrightarrow{
- AC
- }\)\(=\overrightarrow{
- AB
- }+\overrightarrow{
- BC
- }=a+b\)
这就是三角形法则
这是
加法
那么
减法?
由几何意义得
如图
- \(\because \overrightarrow{
- BC'}=-\overrightarrow{BC}\)
- \(\therefore \overrightarrow{BC'
- }=-b\)
又由三角形法则的加法得
\(\overrightarrow{AC'}=\overrightarrow{AB}+\overrightarrow{BC'}=a+(-b)=a-b\)
由此得出 \(a-b\)的矢量表示
3. 平行四边形法则
这个法则是由三角形法则扩展而成
其实本质和三角形法则一样
如图, 由三角形法则得出, 不同方向的线段相加的结果
在这里引入
矢量的叉乘
如图
设 \(P=\overrightarrow{OP},Q=\overrightarrow{OQ}\),
\(P\times Q=\)\(\begin{vmatrix} x1 & y1 \\ x2 & y2 \end{vmatrix}\)
也就是 \(P\times Q=x1\times y2-x2\times y1\)
同时 \(Q\times P=x2\times y1-x1\times y2\)
因此我们可以得到 \(P\times Q=-(Q\times P)\)
所以可以分类讨论得
若 \(P\times Q>0\) 则 \(\overrightarrow{OP}\)在 \(\overrightarrow{OQ}\)的顺时针方向
若 \(P\times Q<0\) 则 \(\overrightarrow{OP}\)在 \(\overrightarrow{OQ}\)的逆时针方向
若 \(P\times Q=0\) 则 \(\overrightarrow{OP},\overrightarrow{OQ}\)共线
由此推得
右手法则: 一个简单的确定向量的方向的方法是这样的: 右手的四指从 a 以不超过 180 度的转角转向 b 时, 竖起的大拇指指向是 c 的方向.
则对于有公共端点的线段 \(\overrightarrow{P_{0}P_{1}}\)和 \(\overrightarrow{P_{1}P_{2}}\), 通过计算 \((P_{2}-P_{0})\times (P_{1}-P_{0})\)的符号确定折线方向(重点)
因此, 可以用这个方法来做凸包
二, 凸包
1. 定义: 凸包是啥? 就是给你一堆点, 然后用一根有弹性的橡皮筋包住所有的点, 这个橡皮筋就是一个凸包. 题目可能会让你求构成凸包的点或者是凸包的长度或围成的面积
2. 怎么求凸包
第一步:
在这里, 我们要求 \(y\)值最小的点, 我们可以用 \(sort\)排序
- \(cmp:\)
- bool cmp(edge a,edge b)
- {
- if(a.y==b.y)return a.x<b.x;
- else return a.y<b.y;
- }
- for(int i=1;i<=n;i++)scanf("%lf %lf",&tain[i].x,&tain[i].y);
- sort(tain+1,tain+1+n,cmp);
第二步:
在图中, 我们可以看到, 我们要选择的点最优是极角最小的点, 也是我们每次都要往顺时针方向走, 所以我们在一开始排完序后, 要进行极角排序, 再进行顺逆时针判断, 满足是顺时针的最小极角就是我们要的点
极角排序有两种方法:
- bool cmp(node a,node b)// 极角排序另一种方法, 速度快
- {
- if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
- return (atan2(a.y-yy,a.x-xx))<(atan2(b.y-yy,b.x-xx));
- return a.x<b.x;
- }
- //atan2 是一个函数, 返回的是原点至点 (x,y) 的方位角, 即与 x 轴的夹角.
- ------------
- bool cmp(node a,node b)// 极角排序普通
- {
- int m=cross(vex[0],a,b);
- if(m>0)
- return 1;
- else if(m==0&&dis(vex[0],a)-dis(vex[0],b)<=0)
- return 1;
- else return 0;
- }
接下来就是循环, 寻找满足在逆时针的点, 这就涉及到求叉积
求叉积:
- double cross(edge a,edge b,edge c)
- {
- return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
- }
循环:
- for(int i=3;i<=n;i++)
- {
- while(cross(convex[tot-1],convex[tot],tain[i])<0)tot--;
- convex[++tot]=tain[i];
- }
后面的就比较基础, 不仔细讲了
放代码:
- #include<bits/stdc++.h>
- using namespace std;
- const int N=10010;
- int n;
- struct edge
- {
- double x,y;
- };
- edge tain[N],convex[N];
- double xx,yy;
- double dis(edge a,edge b)// 两点直线距离公式
- {
- return sqrt((a.x-b.x)*(a.x-b.x)*1.0+(a.y-b.y)*(a.y-b.y));
- }
- double cross(edge a,edge b,edge c)// 计算叉积
- {
- return (b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y);
- }
- bool cmp(edge a,edge b)
- {
- if(a.y==b.y)return a.x<b.x;
- else return a.y<b.y;
- }
- bool cmp1(edge a,edge b)
- {
- if(atan2(a.y-yy,a.x-xx)!=atan2(b.y-yy,b.x-xx))
- return atan2(a.y-yy,a.x-xx)<atan2(b.y-yy,b.x-xx);
- return a.x<b.x;
- }
- int main()
- {
- scanf("%d",&n);
- for(int i=1;i<=n;i++)
- scanf("%lf %lf",&tain[i].x,&tain[i].y);
- sort(tain+1,tain+1+n,cmp);
- convex[1]=tain[1];
- xx=convex[1].x;
- yy=convex[1].y;
- sort(tain+2,tain+1+n,cmp1);
- int tot=2;
- convex[2]=tain[2];
- for(int i=3;i<=n;i++)
- {
- while(cross(convex[tot-1],convex[tot],tain[i])<0)tot--;
- convex[++tot]=tain[i];
- }
- double ans=0;
- for(int i=2;i<=tot;i++)
- ans+=dis(convex[i-1],convex[i]);
- ans+=dis(convex[1],convex[tot]);
- printf("%.2lf",ans);
- return 0;
- }
- /*
- 4
- 4 8
- 4 12
- 5 9.3
- 7 8
- */
深深的明白自己的渺小
矢量及[模板] 二维凸包
来源: http://www.bubuko.com/infodetail-3156030.html