題目鏈接
把線段以斜率為第一關(guān)鍵字，截距為第二關(guān)鍵字升序排序。
然后維護一個單調(diào)棧，保證棧中兩兩線段的交點的\(x\)坐標(biāo)單調(diào)上升就行了。棧中的線段即為所求。

#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 50010; struct Seg{double k, b;int id;int operator < (const Seg A) const{return k == A.k ? b < A.b : k < A.k;} }s[MAXN]; int n; int st[MAXN], top; inline int cmp(int a, int b){return s[a].id < s[b].id; } double calc(int a, int b){return (s[b].b - s[a].b) / (s[a].k - s[b].k); } int main(){scanf("%d", &n);for(int i = 1; i <= n; ++i){scanf("%lf%lf", &s[i].k, &s[i].b);s[i].id = i;}sort(s + 1, s + n + 1);st[++top] = 1;for(int i = 2; i <= n; ++i){while(top && s[i].k == s[st[top]].k || top > 1 && calc(i, st[top - 1]) <= calc(st[top], st[top - 1])) --top;st[++top] = i;}sort(st + 1, st + top + 1, cmp);for(int i = 1; i <= top; ++i)printf("%d ", s[st[i]].id);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Qihoo360/p/10322557.html

總結(jié)

以上是生活随笔為你收集整理的【洛谷 P3194】 [HNOI2008]水平可见直线 （单调栈）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。