WuTao's Blog

while(!(succeed = try()));

0%

计算几何模板整理

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 4k 阅读时长 ≈ 4 分钟 
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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
const db eps = 1e-10;  // 误差
const db pi = acos(-1.0);  // 圆周率
const ll inf = 0x3f3f3f3f3f3f3f3f;  // 无穷大
const ll maxn = 1e5 + 10;

// 精度三态函数
inline int dcmp(db x) {
    if(fabs(x) < eps) return 0;
    return x > 0? 1: -1;
}

class Point {
public:
    double x, y;
    Point(double x = 0, double y = 0) : x(x), y(y) {}  // 构造器
    // 输入
    void input() {
        scanf("%lf%lf", &x, &y);
    }
    // 一般用于排序
    bool operator<(const Point &a) const {
        return (!dcmp(x - a.x))? dcmp(y - a.y) < 0: x < a.x;
    }
    // 判断点的坐标是否相同
    bool operator==(const Point &a) const {
        return dcmp(x - a.x) == 0 && dcmp(y - a.y) == 0;
    }
    // 点到点的距离的平方
    db dis2(const Point a) {
        return pow(x - a.x, 2) + pow(y - a.y, 2);
    }
    // 点到点的距离
    db dis(const Point a) {
        return sqrt(dis2(a));
    }

    // 向量的模的平方
    db dis2() {
        return x * x + y * y;
    }
    // 向量的模
    db dis() {
        return sqrt(dis2());
    }
    // 向量加法
    Point operator+(const Point a) {
        return Point(x + a.x, y + a.y);
    }
    // 向量减法
    Point operator-(const Point a) {
        return Point(x - a.x, y - a.y);
    }
    // 向量数乘
    Point operator*(double p) {
        return Point(x * p, y * p);
    }
    // 向量数除
    Point operator/(double p) {
        return Point(x / p, y / p);
    }
    // 向量点积
    db dot(const Point a) {
        return x * a.x + y * a.y;
    }
    // 向量叉积
    db cross(const Point a) {
        return x * a.y - y * a.x;
    }
    // 向量与 a 向量的夹角
    db ang(Point a) {
        return acos((a.dis() * dis()) / dot(a));
    }
    // 向量在 b 向量上的投影
    db projection(Point b) {
        if(dcmp(dis()) == 0) return 0;
        if(dcmp(b.dis()) == 0) return dis();
        return cos(ang(b)) * dis();
    }
    // 向量逆时针旋转 rad 弧度
    Point Rotate(double rad) {
        return Point(x * cos(rad) - y * sin(rad), x * sin(rad) + y * cos(rad));
    }

};
typedef Point Vector;

class Line {
public:
    Point s, e;
    Line(Point s, Point e) : s(s), e(e) {}
    // 点 p 在有向线段 se 的左边返回 1, 右边返回 -1
    int toLeftTest(Point p) {
        if((e - s).cross(p - s) > 0) return 1;
        else if((e - s).cross(p - s) < 0) return -1;
        return 0;
    }
    // 直线与直线位置关系 0-重合 1-平行 2-相交
    int linecrossline (Line l) {
        if(dcmp((e - s).cross(l.e - l.s)) == 0) {
            if(dcmp((l.s - e).cross(l.e - s)) == 0) {
                return 0;
            }
            return 1;
        }
        return 2;
    }
    // 直线与直线交点
    Point crosspoint(Line l) {
		double a1 = (l.e - l.s).cross(s - l.s);
		double a2 = (l.e - l.s).cross(e - l.s);
        double x = (s.x * a2 - e.x * a1) / (a2 - a1);
        double y = (s.y * a2 - e.y * a1) / (a2 - a1);
        if(dcmp(x) == 0) x = 0;
        if(dcmp(y) == 0) y = 0;
		return Point(x, y);
	}
};

// 凸包
typedef vector<Point> Polygon;
Polygon Andrew(vector<Point> p) {
    int n = p.size(), cnt = 0;
    Polygon ans(2 * n);
    sort(p.begin(), p.end());
    for (int i = 0; i < n; ++i) {
        while (cnt >= 2 && (ans[cnt - 1] - ans[cnt - 2]).cross(p[i] - ans[cnt - 2]) < eps) {
            --cnt;
        }
        ans[cnt++] = p[i];
    }
    int t = cnt + 1;
    for (int i = n - 1; i > 0; --i) {
        while (cnt >= t && (ans[cnt - 1] - ans[cnt - 2]).cross(p[i - 1] - ans[cnt - 2]) < eps) {
            --cnt;
        }
        ans[cnt++] = p[i - 1];
    }
    ans.resize(cnt - 1);
    return ans;
}

// 判断点在线段上
bool OnSegment(Point p, Point a1, Point a2) {
    return dcmp((a1 - p).cross(a2 - p)) == 0 && dcmp((a1 - p).dot(a2 - p)) < 0;
}

// 判断线段相交
bool Intersection(Point a1, Point a2, Point b1, Point b2) {
    double c1 = (a2 - a1).cross(b1 - a1), c2 = (a2 - a1).cross(b2 - a1),
            c3 = (b2 - b1).cross(a1 - b1), c4 = (b2 - b1).cross(a2 - b1);
    return dcmp(c1) * dcmp(c2) < 0 && dcmp(c3) * dcmp(c4) < 0;
}

// 判断点在凸包内
int isPointInPolygon(Point p, vector<Point> s) {
    int wn = 0, cc = s.size();
    for (int i = 0; i < cc; i++) {
        Point p1 = s[i];
        Point p2 = s[(i + 1) % cc];
        if (p1 == p || p2 == p || OnSegment(p, p1, p2)) return -1;
        int k = dcmp((p2 - p1).cross(p - p1));
        int d1 = dcmp(p1.y - p.y);
        int d2 = dcmp(p2.y - p.y);
        if (k > 0 && d1 <= 0 && d2 > 0) wn++;
        if (k < 0 && d2 <= 0 && d1 > 0) wn--;
    }
    if (wn != 0) return 1;
    return 0;
}

// 凸包面积
double PolygonArea(Polygon p) {
    double ans = 0;
    for(int i = 2; i < p.size() - 1; ++i) {
        ans += abs((p[i] - p[1]).cross(p[i + 1] - p[1]));
    }
    return ans * 0.5;
}

(更新中)

欢迎关注我的其它发布渠道