优雅的复数旋转 & 坐标变换方法

發表於2026-06-01|更新於2026-06-15|邏輯與算法知識

|總字數:226|閱讀時間:1分鐘|瀏覽量:

【XCPC/ 计算几何】优雅的复数旋转 & 坐标变换方法

给定二维平面的区域是一条以原点为端点的射线和所有距离射线 \leqslant d 的点的集合。射线的初始方向向量给定，会以每个单位时间 1 弧度的顺序旋转。给定一个 n 个顶点的凸多边形，保证凸多边形目标距离原点 >d。求区间在时间 [0,t] 中区域与凸多边形有交的时间区间长度。

法向量： $\boldsymbol{n} = (A, B)$
方向向量： $\boldsymbol{u}=(-B, A)$
单位方向向量： $\boldsymbol{u}_{0} = \frac{(-B, A)}{||\boldsymbol{n}||}$
平行分量（投影） $t = \boldsymbol{P} \cdot \boldsymbol{u}$
垂直分量（距离） $d = \frac{|\boldsymbol{P} \cdot \boldsymbol{n} + C|}{||\boldsymbol{n}||}$

文章作者: 小明同學

文章連結: http://kobicgend.top/posts/a4cdb5a.html

版權聲明: 本部落格所有文章除特別聲明外，均採用CC BY-NC-SA 4.0 授權協議。轉載請註明來源小明の雜貨屋！

ACM 筆記算法

相關推薦

【组合计数杂谈】三道 Bingo 游戏题（备份）

本文涉及的知识点：组合数公式，古典概型，Min-Max 反演及推广，卷积优化思想，状态压缩思想与状态压缩 DP，快速数论变换 NTT，快速数论变换 NTT，快速沃尔什变换 FWT。本系列教程「以题带讲」，以典型题目为载体，着重讲解知识点的适用条件和使用方法，而规避复杂的理论推导。我不擅长数学，对 CF 和区域赛的数学题，从简单计算到数论组合都望而却步。「tag 是数学吗那不做了。」可能是因为网上的教程大多是罗列定理，给出大段证明，最后放几个例题链接。我没有耐心和能力读完整篇文章。 2024 ICPC World Finals Astana B. Bingo for the Win! Bingo 游戏，nnn 个人每人要抢 kkk 个数，主持人按随机顺序依次报数，报到每个数 [1,109][1,10^{9}][1,109] 的概率相同。已知如果有多名选手要抢某个数字，那么编号小的选手总是优先抢到。问每个人成为最后一名（其他人都抢完了但自己还没抢完）的概率。 ...

Good Bye 2024: 2025 is NEAR A - E

无向图有边权。有 qqq 个形式为 (a,b,k)(a, b, k)(a,b,k) 的查询：从顶点 aaa 到顶点 bbb 的所有路径中，找出路径上第 kkk 大边权的最小值。n⩽400, q⩽3×105n \leqslant 400,\ q \leqslant 3 \times 10^{5}n⩽400, q⩽3×105。枚举答案 www，把边权 ⩽w\leqslant w⩽w 的变成 0，>w> w>w 的变成 1。如果 da→b<kd_{a\to b}<kda→b<k，就说明答案 ⩽w\leqslant w⩽w。

二分转化为 01 串如果某个问题满足：如果序列只有 0\mathtt{0}0 和 1\mathtt{1}1，问题是易解决的答案依赖于序列中的数的大小关系单次询问可以考虑二分答案（或计算答案的中间变量）为 xxx，将序列中 ⩾x\geqslant x⩾x 的数置为 111，否则将 <x<x<x 的数置为 000（或 −1-1−1，按需），将序列转化为 01\mathtt{01}01 串。【求中位数】x=an+12′x = a'_{\frac{n+1}{2}}x=a2n+1′，其中将 aaa 数组排序后为 a′a'a′。⩾x\geqslant x⩾x 的个数比 <x< x<x 的个数恰好要多，因此可以通过二分出一个最大的满足上述整数得到中位数。值得注意的是，如果中位数定义为 an+12a_{\frac{n+1}{2}}a2n+1，将 ⩾x\geqslant x⩾x 的数置为 111，定义为 an2a_{\frac{n}{2}}a2n，将 >x> x>x...

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121struct Node { std::array<Node*, 2> next{}; int icnt = 0;};void insert(Node*& p, int val, int bit = 30) { if (!p) { p = new Node(); } p->icnt++; if (bit == -1) return; ...

给定长度为 NNN 的序列 A=[A1,A2,…,AN]A = [A_1, A_2, \dots, A_N]A=[A1,A2,…,AN]。定义其一个有效分拆为将其切分为 kkk 个相邻的子数组，各段长度依次为 L1,L2,…,LkL_1, L_2, \dots, L_kL1,L2,…,Lk（满足 Li≥1L_i \ge 1Li≥1 且 ∑i=1kLi=N\sum_{i=1}^k L_i = N∑i=1kLi=N）。令第 iii 个子数组的起始下标为 Si=1+∑j=1i−1LjS_i = 1 + \sum_{j=1}^{i-1} L_jSi=1+∑j=1i−1Lj。序列 AAA 被认为是合法的，当且仅当存在一种分拆同时满足以下两种条件：条件 1（Type 1）：对于所有子数组，其首元素等于该段长度减一。 ∀i∈[1,k],ASi=Li−1\forall i \in [1, k], \quad A_{S_i} = L_i - 1 ∀i∈[1,k],ASi=Li−1 条件 2（Type 2）：第一段长度为 111...

Codeforces Round 982 (Div. 2)

A. Rectangle Arrangement 取最大值的正确性：凸阶梯形平移后即是矩形，其周长与矩形周长相等。 123456789101112131415161718192021222324252627#include <bits/stdc++.h>using namespace std;using ll = long long;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; int X = 0, Y = 0; while (n--) { int x, y; cin >> x >> y; X = max(X, x); Y = max(Y, y); ...

評論