Codeforces 975E Hag's Khashba 【口头AC】【计算几何】

E题可能我现在的水平只能是口头AC的程度...

原本看了题目连模拟都不知道怎么模拟,因为不知道两个钉子拿走一个后多边形会怎么rotate。在问了物理大佬后,知道多边形的质心最终会落到【剩下那个钉子】的正下方。因为此时【钉子给质心的拉力】=【重心受到的重力】且方向相反,只有这个点是平衡点。(实际上如果没有摩擦力的话,这个多边形会一直做单摆运动)之后我们对每个q维护多边形第一个点i(任意一个点都可以)和质心O的坐标,每次通过这两个可以得到所有剩下的点。(因为多边形的形状不变,∠iOj = ∠i‘O’j‘,边长也固定)

复杂度为O(q)

原文地址:https://www.cnblogs.com/ZhenghangHu/p/8984544.html