walkalone

分类

题解(77)

/ 注册

全部文章（共5篇）

2022 年牛客多校第八场 K 题题解

K Symmetry: Convex 题意：给定 nnn 个点的凸多边形 CnC_nCn，输出前 iii 个点构成的凸包的对称轴。n≤1×105n \leq 1\times 10^5n≤1×105。解法：找对称轴可以使用 Manacher。本题先预处理整个凸包构成的串的 Manacher（注意不...

计算几何字符串

2022-08-14

0 351

牛客多校第七场 B 题题解

B 题题意：给定平面上一 nnn 个点的整点凸多边形，使其绕着任意对称轴在空间中旋转，求其扫过的体积。若无对称轴则输出 000。n≤1×105n \leq 1\times 10^5n≤1×105。解法：由于是整点多边形，因而对称轴至多不超过 O(log⁡n)O(\log n)O(logn) 条，可...

计算几何

2022-08-11

2 435

牛客多校第四场 M 题题解

M Monotone Chain M 题题意：给定平面 nnn 个点 (xi,yi)(x_i,y_i)(xi,yi)，找到两个向量 a,b\textbf{a},\textbf{b}a,b 满足 ∀1≤i≤j≤n\forall 1 \leq i \leq j \leq n∀1≤i≤j≤n，(OAi...

计算几何

2022-07-31

1 295

牛客多校第四场 B 题题解

B 2D Internet Angel B 题题意：给定内外同心圆，半径分别为 R1,R2R_1,R_2R1,R2，沿内侧圆外有一 nnn 边外接多边形 {Pi}\{P_i\}{Pi}，与内侧圆的切点为 {Qi}\{Q_i\}{Qi}，保证这一多边形完全在外侧圆内。记此外接多边形外与外侧圆内...

计算几何数值积分

2022-07-31

1 269

牛客多校第二场 B 题题解

B Light B 题题意：给定一个凸多边形 {Cn}\{C_n\}{Cn}，在这一多边形向内延申 www 的范围有一堵高为 hhh 的墙，墙内多边形记为 C′C'C′。现在在点 L(x,y,z)L(x,y,z)L(x,y,z) 处有一点光源，问该点光源照射到 C′C'C′ 的面积。n≤2×103...

计算几何

2022-07-29

0 352