P1691 [ICPC 2016 WF] Oil 题解

· · 题解

题面解释：

平面内有一些线段，你可以选择一条直线，最大化与这条直线有交点的线段的长度之和。

思路分析：

直线有无数条，我们需要限制这个直线使其可以被枚举。容易发现一定存在一条最优直线同时过至少两个线段的端点，否则我们可以略微移动之使其交到端点上。那么我们可以枚举两个端点，两点确定一条直线，那么一共有 O(n^2) 级别的直线，每条直线再枚举 n 条线段，发现复杂度达到了 O(n^3)。

这个做法似乎没有什么前途，我们很难使用数据结构来优化。两点可以确定直线，但直线还有点斜式，我们可以枚举一个点和，然后枚举斜率来确定直线。斜率也要求是要过别的点，所以直线数量依旧 O(n^2) 级别，接下来就是如何快速求出每条直线对应的答案。

直线去对应线段不好做，考虑用线段对应直线。先枚举每条线段（与已确定的端点不在同一高度），分别与其左右端点相交就可以求出其做出贡献的区间。再扫一遍求出区间最大值即可。每个点入队一次，出队一次，单次时间复杂度 O(n)，2\times n 个端点，总复杂度 O(n^2)。