bzoj 3311: [Usaco2013 Nov]Line of Sight 计算几何?

题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=3311


一道看上去挺难的,其实很简单的题

拿一个官方题解上的图片

首先我们要知道一个小结论:如果两个点可以互相看到,那么它们能看到的弧也一定是相交的

为了方便起见,我们转成弧度来进行计算

我们可以很简单的求出PQ,R也是已知的,所以直接就可以求出α的大小

有一个好用的函数:atan2(y,x)

可以求出以弧度来表示的,(x,y)与x轴的夹角,atan2比atan要稳定

所以我们就可以知道了一个点能看到的弧的两个端点,全都放进一个数组里,排个序之后用单调栈计算一下就好了

防止发生什么奇怪的问题,所以我们跑两圈,第二圈的时候再统计答案

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注