一、矢量
1.定义：是一条有方向的线段的长度
如图，(a)就是线段(overrightarrow{AB})的矢量
2.三角形法则
如图
(ecause overrightarrow{AB})(=a)，(overrightarrow{BC})(=b)
( herefore overrightarrow{AC})(=overrightarrow{AB}+overrightarrow{BC}=a+b)
这就是三角形法则
这是
加法
那么
减法？
由几何意义得
如图
(ecause overrightarrow{BC'}=-overrightarrow{BC})
( herefore overrightarrow{BC'}=-b)
又由三角形法则的加法得
(overrightarrow{AC'}=overrightarrow{AB}+overrightarrow{BC'}=a+(-b)=a-b)
由此得出(a-b)的矢量表示
3.平行四边形法则
这个法则是由三角形法则扩展而成
其实本质和三角形法则一样
如图，由三角形法则得出，不同方向的线段相加的结果
在这里引入
矢量的叉乘
如图
设(P=overrightarrow{OP},Q=overrightarrow{OQ})，
(P imes Q=)(egin{vmatrix}
x1 & y1 \
x2 & y2
end{vmatrix})
也就是(P imes Q=x1 imes y2-x2 imes y1)
同时(Q imes P=x2 imes y1-x1 imes y2)
因此我们可以得到(P imes Q=-(Q imes P))
所以可以分类讨论得
-
若(P imes Q>0) 则(overrightarrow{OP})在(overrightarrow{OQ})的顺时针方向
-
若(P imes Q<0) 则(overrightarrow{OP})在(overrightarrow{OQ})的逆时针方向
-
若(P imes Q=0) 则(overrightarrow{OP},overrightarrow{OQ})共线
由此推得
右手法则：一个简单的确定向量的方向的方法是这样的：右手的四指从a以不超过180度的转角转向b时，竖起的大拇指指向是c的方向。
则对于有公共端点的线段(overrightarrow{P_{0}P_{1}})和(overrightarrow{P_{1}P_{2}})，通过计算((P_{2}-P_{0}) imes (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
*/
深深的明白自己的渺小