前提条件

1
2
3
4
5
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
typedef double temType; // 需要用到的类型

点(向量)

已知

$(x,y)$,点坐标或向量坐标

函数

相加、相减、与常数相加、点乘、叉乘、旋转、标准化

向量旋转

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// 点或向量
struct point{
temType x, y;
point(): x(0), y(0){}
point(temType _x, temType _y): x(_x), y(_y){}
point(const point &t){x = t.x;y = t.y;};
point operator-(const point& t) const{return {x-t.x, y-t.y};} // 相减
point operator+(const point& t) const{return {t.x+x, t.y+y};} // 相加
point operator*(temType t) const{return {x*t, y*t};} // 与常数相乘
temType cdot(const point& t) const{return t.x*x+t.y*y;} // 点乘
temType times(const point& t) const{return x*t.y-y*t.x;} // 叉乘
bool operator==(const point& t) const{return x==t.x && y==t.y;}
bool operator!=(const point& t) const{return x!=t.x || y!=t.y;}
temType length() const{return sqrt(x*x+y*y); }
void normalize() { //标准化
temType sqt = sqrt(x*x+y*y);
x = x/sqt; y = y/sqt;
}
point rotation(temType t) const{ //向量旋转
temType cost=cos(t), sint=sin(t);
return {x*cost-y*sint, x*sint+y*cost};
}
};
typedef struct point pit;
typedef struct point vtr;

极坐标点

1
2
3
4
5
6
7
8
struct polar{
temType p, e;
polar(temType _p, temType _e): p(_p), e(_e){}
};
typedef struct polar plr;

polar toPolar(const pit& t){ return {sqrt(t.x*t.x+t.y*t.y),atan2(t.y,t.x)}; }
pit toRect(const plr& t){ return {t.p*cos(t.e), t.p*sin(t.e)}; }

线段

已知

已知线段两端端点$A,B$

函数

跨立实验,快速排斥实验

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 线段
struct segment{
pit A, B;
segment(const pit& _A, const pit& _B): A(_A), B(_B){}
pit midpoint() const{return {(A.x+B.x)/2.0, (A.y,B.y)/2.0};} // 中点
bool rapidRejectionExp(const segment& t) const { // 快速排斥实验 TODO 这里有一些错误
pit minTmp(min(A.x, B.x), min(A.y, B.y));
pit maxTmp(max(A.x, B.x), max(A.y, B.y));
return (t.A.x >= minTmp.x && t.A.x <= maxTmp.x) && (t.A.y >= minTmp.y && t.A.y <= maxTmp.y) ||
(t.B.x >= minTmp.x && t.B.x <= maxTmp.x) && (t.B.y >= minTmp.y && t.B.y <= maxTmp.y);
}
bool straddleExp(const segment& t) const{ // 跨立实验
// if(!rapidRejectionExp(t)) return false;
vtr AB = B-A, tba = t.A-t.B;
temType t1 = AB.times(t.A-A) * AB.times(t.B-A), t2 = tba.times(A-t.B)*tba.times(B-t.B);
if(t1 < 0 && t2 < 0) return true;
else return false;
}
};
typedef struct segment seg;

直线与射线

已知

已知直线上一点和向量,$P,\vec{s}$

函数

获得直线上的一点

求两直线交点

公式

代码

1
2
3
4
5
6
7
8
9
10
11
struct line{
pit P;
vtr s;
line(const pit& _P, const vtr& _s): P(_P), s(_s) {s.normalize();}
pit getPoint(temType t) const {return P + s*t;}
bool ispParallel(const line& t) const{return s.times(t.s)==0;} // 平行
bool isCoincide(const line& t) const{return s.times(t.s)==0 && ((s.times(P-t.P)==0));} // 重合
pit intersection(const line& t) const{ return P - s * (t.s.times(P-t.P) / t.s.times(s)); }
};
typedef struct line line; // 直线
typedef struct line ray; // 射线

已知

圆心$O$,半径$r$

代码

1
2
3
4
5
6
struct circle{
pit O;
temType r;
circle(const pit& _O, temType _r): O(_O), r(_r){}
};
typedef struct circle cle;

直线与圆

已知

直线:$P$点坐标$(P_x,P_y)$,$\vec{s}=(s_x,s_y)$

圆:$O$点坐标$(O_x,O_y)$,圆的半径$r$

推导

代码

1
2
3
4
5
6
seg intersectionOfLineAndCircle(const line& p, const cle& c){
vtr PO = c.O - p.P;
temType OE = p.s.times(PO), PE = p.s.times(PO);
temType tmp = sqrt(c.r*c.r-OE*OE);
return {p.getPoint(PE-tmp), p.getPoint(PE+tmp)};
}

凸包

已知

已知一个二维坐标图中每个顶点,求最小周长能够包含所有所有顶点的凸包

思路

先将点双关键字排序,横坐标为第一关键字,纵坐标为第二关键字

排序之后

图片向量方向迭代方向

之后维护单调单调栈,其中栈顶为$S_1$,栈顶第二元素为$S_2$,当前检查的点为$P$,由于凸包是不会出现右转的,所以当出现$\vec{S_2S_1}\times\vec{S_1P}<0$说明栈顶的元素不是最优凸包,弹出栈顶重复上一步。

第一次循环迭代之后,会发现求完了下凸包先在需要倒转迭代方向,再次遍历

第二次迭代完善上凸包,最终会形成一个最短周长的能够包含所有顶点的凸包

注意:运行结果最后还会添加一次初始节点,那么周长就为

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const int N = 1e5+10;
pit p[N];
int stk[N<<1];
int tp;

bool cmp(pit &a, pit &b){
if(a.x == b.x) return a.y < b.y;
return a.x < b.x;
}

int main() {
debug;
int n;
temType xt, yt;
cin >> n;
for(int i = 0; i < n; ++i) {
cin >> xt >> yt;
p[i] = point(xt, yt);
}
sort(p, p+n, cmp);
stk[++tp] = 0;
for(int i = 1; i < n; ++i) {
while (tp >= 2 && ((p[stk[tp]]-p[stk[tp-1]]).times(p[i]-p[stk[tp]]) < 0)) tp--;
stk[++tp] = i;
}
int tmp = tp;
for(int i = n-1; i >= 0; --i){
while (tp > tmp && ((p[stk[tp]]-p[stk[tp-1]]).times(p[i]-p[stk[tp]]) < 0)) tp--;
stk[++tp] = i;
}
temType ans = 0;
for(int i = 1; i <= tp; ++i) {
ans += (p[stk[i]] - p[stk[i-1]]).length();
}
printf("%.2f", ans);
}

本文采用CC-BY-SA-3.0协议,转载请注明出处
作者: Csome