题目传送门(BZOJ)
>原文链接<

题解 :

如果会了斜率优化, 这道题做起来很简单.

首先把所有直线按斜率排序, 斜率大的肯定不会被斜率小的盖上, 如果斜率一样, 按截距排序.

然后按这个顺序一条一条把直线入栈,

若后来的直线斜率和栈顶斜率一样, 那么栈顶必定没有用, 弹出(因为截距小)

若栈顶和第二栈顶的交点在这条线和栈顶的交点右侧, 那么栈顶必然没用, 弹出 (因为这条直线和第二栈顶完全覆盖了栈顶)

就这么一条一条插, 最后统计答案, 代码实现简单, 如果弹出部分不是很懂, 可以看看代码

代码 :

#include <cmath>#include <cstdio>#include <iostream>#include <algorithm>#define f2 doubleconst int N = 51000;const f2 eps = 1e-6;using namespace std;struct Node { f2 a, b; int idx; bool operator < (const Node &A) const { return fabs(a-A.a) < eps ? b < A.b : a < A.a; }}a[N], s[N];bool ans[N];int top, n;f2 calc(const Node &x1, const Node &x2) { return (x2.b-x1.b)/(x1.a-x2.a);}void insert(Node a) { while(top) { if(fabs(s[top].a-a.a) < eps)top--; else if(top > 1 && calc(a, s[top-1]) <= calc(s[top], s[top-1])) top--; else break; } s[++top]=a;}int main() { scanf("%d", &n); for(int i = 1; i <= n; i ++ ) { scanf("%lf%lf", &a[i].a, &a[i].b); a[i].idx = i; } sort(a+1, a+n+1); for(int i = 1; i <= n; i ++ ) insert(a[i]); for(int i = 1;i <= top; i ++ ) ans[s[i].idx] = 1; for(int i = 1; i <= n; i ++ ) if(ans[i]) printf("%d ",i);}