这可能是我电脑上唯一一个可以记中文还可以打代码还可以保存的地方了 so sad
决定跟着cls的课件过一遍
要把几个板子囤好 (据说PKU爱考寄蒜几盒板子)
不过我发现一到markdown下我就喜欢折腾
感觉排版突然就重要了起来
- 向量结构体与基本运算
typedef double db;
struct po{
db x,y;
po (db x=0,y=0):x(x),y(y) {}
};
const db eps=1e-9;
po operator + (po a,po b) { return po(a.x+b.x,a.y+b.y); }
po operator - (po a,po b) { return po(a.x-b.x,a.y-b.y); }
po operator * (po a,db b) { return po(a.x*b,a.y*b); }
po operator / (po a,db b) { return po(a.x/b,a.y/b); }
db sqr(db x) { return x*x; }
db dis(po a,po b) { return sqrt(sqr(a.x-b.x)+sqr(a.y-b.y)); }
int cmp(db x) { return fabs(x)<eps?0:(x<0?-1:1); }
bool operator == (po a,po b) { return (!cmp(a.x-b.x))&&(!cmp(a.y-b.y)); }
- 点积与叉积
点积是个值 而叉积是个向量
用的更多的大概是叉积？
点积 -> x1x2+y1y2 叉积 ->x1y2-x2y1
点积是一个向量到另一个向量的投影 乘cos 可以用于求cos
叉积是垂直与ab向量所成平面的向量 是两向量间所成平行四边形的面积 可以用于求sin
叉积正负可以用于判相对位置
a×b >0 a在b的顺时针方向 a×b==0共线但不一定同方向
理解为a×b就是从a往b扫过去 而从左往右扫为正
db operator ^ (po a,po b) { return a.x*b.x+a.y*b.y; }
db operator * (po a,po b) { return a.x*b.y-a.y*b.x; }
点/叉积的一些应用
-
折线拐向
首先把两点转为一个向量 判断向量之间的相对位置
v1=p2-p0 v2=p1-p0
讨论v1×v2 <0向右拐 >0向左拐 ==0共线 请用移动的视角来判断左右！！！ -
点在线段上
如果是直线很好办 叉积一下判0即可
如果是线段就要避免在延长/反向延长线上 那么判断一下min/max就好 -
判线段p0p1与直线q0q1是否相交
由于快要没时间了就不看两线段的问题了
令v1=p0-q0,v2=p1-q0,v2=q1-q0 使v1v2与v2v3同号即可使p0 p1分居直线两侧 -
点到线段距离
记住叉积是平行四边形面积 那么就出然后除底边就好
首先要判垂足是否在线段上 不在则表现为cos为负
而且cos可以反映出离哪边比较近 -
求交点
可以暴力表达式或者用点和方向表示向量 -
极角排序
一判象限 二判叉积(根据顺逆定正负) 三判x轴距离
int xx(po a){
if (a.x>0&&a.y>=0) return 1;
if (a.x<=0&&a.y>0) return 2;
if (a.x<0&&a.y<=0) return 3;
return 4;
}
bool jcmp(po a,po b){
if (a==b) return 1;
po x=a-o,y=b-o; int l=xx(x),r=xx(y);
if (l==r) return (x*y<0)||(x*y==0&&x.x<y.x);
return l<r;
}
- 多边形面积
化成三角形来搞 排个序然后每次叉积最后/2
db polys(po *p,int n){
db res=0;
for (int i=1;i<n-1;++i) res+=(p[i]-p[0])*(p[i+1]-p[0]);
return res/2;
}
- 凸包
先排序 直接按x,y分别为关键字
先丢两个点进去 然后从第三个点开始
while不是在之前方向的左边就弹 符合就加进去
做两遍 分别求出下/上凸包
bool tbcmp (po a,po b) { return a.x==b.x?a.y<b.y:a.x<b.x; }
int tb(po *p,int n){
sort(p+1,p+n+1,chcmp);
int m=0;
for (int i=1;i<=n;++i){
while (m>1&&(st[m]-st[m-1])*(a[i]-st[m-1])<0) m--;
st[++m]=a[i];
}
int k=m;
for (int i=n-1;i;--i){
while (m>k&&(st[m]-st[m-1])*(a[i]-st[m-1])<=0) m--;
st[++m]=a[i];
}
return m;
}
注意几点细节 第一次弹栈要保证至少有两个元素 第二次要保证大于下凸包元素
然后两次都是<0 第二次还要把等于也弹掉
第二次求上凸包从n-1开始 最开始可能要去重
6.旋转卡壳 4 3 ka qiao gif此生难忘系列
求平面最远点对
每个点只可能和对踵点有贡献 然后这东西是O(n)的
我们考虑枚举一条边 然后找到其距离最远的点
会形成三角形 然后面积是单峰的
由于是在凸包上做 所以后面的边的对点一定也是单调在前面的边的后面的
然后由于是判面积 那么丢给叉积搞搞就好 不过这里有一些技巧(觉得自己背不下来 还是手推吧)
把面积比较写成叉积与0比较然后根据叉积是面积有
Cross(A,B) - Cross(A,C) = Cross(A,B-C)
那么就搞一搞就好了
db rc(po *p,int n){
n=tb(p,n),p[0]=p[n];
db ans=0;
for (int i=0,j=1;i<n;++i){
while ((p[i+1]-p[i])*(p[j+1]-p[j])>0) j=(j+1)%n;
ans=max(ans,max(dis(p[j],p[i]),dis(p[j+1],p[i+1])));
}
return ans;
}
这里注意我们从0开始然后使其<n的话就可以用取模的方式循环
以及while那里是没有等于的
然后这东西貌似还可以拿来求两个凸多边形之间的最小距离
枚举其中一个的边 然后另一个就搞点就好 这个也是单调的
- 半平面交 又名半个飞机
先把向量们伪极角排序 然后写个斜率优化??
struct ln{
po p,v;
}l[N];
bool comp(ln x,ln y){
db t=x.v*y.v;
return (t>0)||((t==0)&&x.v*(y.p-x.p)>0);
}//先右后左 如果平行则返通过起点连线与向量方向判定
bool lcmp(ln x,ln y){
if (x.v.y==0&&y.v.y==0) return x.v.x<y.v.x;
if (x.v.y<=0&&y.v.y<=0) return comp(x,y);
if (x.v.y>0&&y.v.y>0) return comp(x,y);
return x.v.y<y.v.y;//逆时针
}
bool left(ln x,po p) { return x.v*(p-x.p)>0; }//点在线左边则点与起点向量在原向量左
po jd(ln x,ln y){
po t=x.p-y.p;
db u=(y.v*t)/(y.v,x.v);
return x.p+u*x.v;
}//利用面积之比 同底高之比
void hpi(){
sort(l+1,l+n+1,lcmp);
int m=0;
for (int i=1;i<=n;++i){
if (l[i].v*l[i-1].v||i==1) m++;//平行特判
l[m]=l[i];
}
int h=1,t=2; s[1]=l[1],s[2]=l[2];
for (int i=3;i<=m;++i){
while (h<t&&left(l[i],jd(s[t],s[t-1]))) t--;
while (h<t&&left(l[i],jd(s[h],s[h+1]))) h++;
s[++t]=l[i];
}
while (h<t&&left(s[h],jd(s[t],s[t-1]))) t--;
while (h<t&&left(s[t],jd(s[h],s[h+1]))) h++;//消除无用
s[++t]=s[h];//形成环
for (int i=h;i<t;++i) p[++cnt]=jd(s[i],s[i+1]);
}
- 动态凸包 大致就用平衡树/cdq来维护凸包 每次加入一个点就找前驱后继来判断这个点是属于在凸包内/直接加入/要删掉其他点的哪种情况就好
不会去学了
大概就是以上
一些套路
枚举特殊点/边 极角排序后利用单调性 还经常可以旋转卡壳
展开叉积 x/y分开处理 二分
另外
上面的板子正确性有待确认
网友评论