luoguP4385 [COCI2009]Dvapravca

原题传送门:>Here<

我们考虑随机选两个点,然后连一条经过这两个点的直线,并向两边扩展。做10000组就可以AC了。

以上是乱搞做法。

我们考虑当平行线平行于$x$轴时怎么办。

在这种情况下,我们只要把点投影到$y$轴上,然后查询最长连续红点就可以了。

其实绝对位置不重要,所以我们只要把点对纵坐标排序就行了。

现在我们考虑旋转平行线。

每次我们只需要把点投影到与平行线垂直的直线上,然后查询最长连续红点。

我们发现旋转平行线时,当两个点构成的直线与平行线平行时,也就说明这两个点的投影重合。那么在旋转前后,两个点的位置会进行交换。

这可以用线段树来维护。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×