当前位置：首页 > news >正文

计算几何

news 2026/8/8 22:00:17

点积

设 \(P(0,0),A(x_1,y_1),B(x_2,y_2)\)

则点积就是：\(\overrightarrow{PA}\cdot \overrightarrow{PB}=x_1x_2+y_1y_2\)

还可以表示成 \(|PA|\cdot|PB|\cdot \cos{\theta}\)

这个点积的意义就是一个向量在另一个向量的投影长度乘以那另一个向量。

根据余弦定理：\(|\overrightarrow{AB}|^2=|\overrightarrow{PA}|^2+|\overrightarrow{PB}|^2-2|\overrightarrow{PA}||\overrightarrow{PB}|\cos\theta\)

然后推式子可得。

这个东西是个数值。

叉积

叉积有个几何意义（只不过这个是在三维或者七维上才能是真的）就是所表示的向量 \(\vec{a}\times \vec{b}\) 是分别垂直于向量 \(\vec{a}\) 和 \(\vec{b}\) 的，然后这个东西的模是 \(|\vec{a}||\vec{b}|\sin\theta\) 的。

然后这个东西可以表示成 \(\vec{a}\) 和 \(\vec{b}\) 组成的平行四边形的面积。

注意：这个 \(\theta\) 是有向角

然后我们这个东西 \(|\vec{a}||\vec{b}|\sin\theta=x_1y_2-x_2y_1\)

叉积有两个优势：判断方向和算面积

极角排序

一般的，我们都是逆时针按照从 \((-1,0)\) 开始排序的，显然可以用 atan2 这个东西排序（这个东西的范围是 \((-\pi, \pi]\)），但是精度误差太大，所以我们用整数的叉积排序。

首先得把环给给判掉，也就是以 x 轴切开，然后判断在哪里，再考虑同一个部分怎么排序

首先考虑平面向量的叉积（标量叉积）。
设 \(\theta \in (-\pi, \pi)\) 为向量 \(\vec{a}\) 到 \(\vec{b}\) 的有向夹角（逆时针为正）。
因为 \(\vec{a} \times \vec{b} = |\vec{a}||\vec{b}|\sin\theta\)，
所以若有 \(\vec{a} \times \vec{b} > 0\)，则 \(\sin\theta > 0\)，此时有 \(\theta \in (0, \pi)\)，
这意味着 \(\vec{a}\) 需逆时针旋转才能到达 \(\vec{b}\)。
反之，若 \(\vec{a} \times \vec{b} < 0\)，则需顺时针旋转。

模板

\(\mathscr{Code:}\)

~~欸，我怎么调了一万年~~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
char buf[1 << 21], *p1 = buf, *p2 = buf;
#define scin static inline
typedef vector<int> vi;
typedef unsigned long long ull;
typedef pair<int ,int> pii;
typedef pair<ll, ll> pll;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
#define getchar() gc()
template <typename T> scin void rd(T& s) {s = 0; char ch = getchar(); bool fu = 0;while (ch < '0' || ch > '9') ch == '-' ? fu = 1 : 0, ch = getchar();while (ch >= '0' && ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();s = fu ? -s : s;
}template <typename T, typename...Args> scin void rd(T& s, Args& ...args) {rd(s), rd(args...);}
template <typename T> scin bool updmin(T& a,T& b) {return a > b ? a = b, true : false;}
template <typename T> scin bool updmax(T& a,T& b) {return a < b ? a = b, true : false;}
template <typename T> scin void updmod(T& a) {a >= mod ? a -= mod : 0;}
template <typename T> scin T updmod(T a,T b) {return a + b >= mod ? a + b - mod : a + b;}const int N = 2e5 + 10;
inline int sign(ll a) {return a < 0 ? -1 : a > 0;}
inline int cmp(ll a, ll b) {return sign(a - b); }
struct P {ll x, y;P() {}P(ll _x, ll _y) : x(_x), y(_y) {}P operator+ (P p) {return {x + p.x, y + p.y}; }P operator- (P p) {return {x - p.x, y - p.y}; }P operator* (ll d) {return {x * d, y * d}; }P operator/ (ll d) {return {x / d, y / d}; }bool operator< (P p) const {int c = cmp(x, p.x);if (c) return c == -1;return cmp(y, p.y) == -1;}bool operator== (P p) const {return !cmp(x, p.x) && !cmp(y, p.y); }ll dot(P p) {return x * p.x + y * p.y; } // 点积ll det(P p) {return x * p.y - p.x * y; } // 叉积ll _abs() {return x * x + y * y; } // 向量的模的平方P rot90() {return P(-y, x); } // 逆时针旋转 90°int quad() const {return y > 0 || !y && x <= 0; } // 若返回 1 则在 x 轴的上方或者在 x 的负半轴上含 O
}a[N];
#define cross(p1, p2, p3) ((p2.x - p1.x) * (p3.y - p1.y) - (p3.x - p1.x) * (p2.y - p1.y)) // 向量 p1p2 和 p1p3 的叉积
#define cross0p(p1, p2, p3) sign(cross(p1, p2, p3))
int cmp_ang(P a, P b) { // re 1 a < b ---|--- re -1 a > bif (a.quad() != b.quad()) return a.quad() < b.quad() ? 1 : -1;ll c = a.det(b);if (c > 0) return 1;if (c < 0) return -1;if (a._abs() < b._abs()) return 1;if (a._abs() > b._abs()) return -1;return 0;
}int n;void Solve() {rd(n);for (int i = 1; i <= n; ++i) rd(a[i].x, a[i].y);sort(a + 1, a + n + 1, [&](P a, P b) {int c = cmp_ang(a, b);if (c == 1) return 1;return 0;});for (int i = 1; i <= n; ++i) cout << a[i].x << " " << a[i].y << "\n";
}signed main() {// freopen("input.in", "r", stdin);// ios::sync_with_stdio(false);// cin.tie(0), cout.tie(0);int T = 1;// rd(T);while (T--) Solve();return 0;
}