Diaosi's blog

Blogs

QOJ 9554 更好写的做法

2025-03-19 18:55:03 By Diaosi

前半段跟标算一样,相当于是求若干射线与凸包的交面积。但是由于旋转中心 $O$ 可能会在凸包的外面或者边界上,这会导致要讨论许多 corner case。

注意到出题人为了避免精度问题把值域开的很小,而根据经典结论,值域为 $\mathcal{O}(V)$ 的严格凸包大小是 $\mathcal{O}\big(V^{2/3}\big)$ 的。换句话说,凸包上有用的边不会太多。对于原本的每个划分区域,我们把划分这个区域的两条射线和凸包的边丢到一起做半平面交,复杂度只有 $\mathcal{O}\big(nV^{2/3}\big)$(预处理排序),而这个时间复杂度是可以接受的。这样就完美地避免了各种分类讨论。

这个做法实际表现是非常优秀的,在使用 long double 的情况下只跑了 243ms/7000ms。

Comments

No comments yet.

Post a comment

You can refer to mike by using "@mike", and "mike" will be highlighted. If you want to type the character "@", please use "@@" instead.

You can enter "/kel" to use the emoticon "kel".