郑州怎么做网站排名,重庆设计集团,网页设计的好处,必应搜索引擎网站题目链接 可以看出我们是要维护一个下凸壳。 先对斜率从小到大排序。斜率最大、最小的直线是一定会保留的#xff0c;因为这是凸壳最边上的两段。 维护一个单调栈#xff0c;栈中为当前可见直线(按照斜率排序)。 当加入一条直线l时#xff0c;可以发现 如果l与栈顶直线l的交…题目链接 可以看出我们是要维护一个下凸壳。 先对斜率从小到大排序。斜率最大、最小的直线是一定会保留的因为这是凸壳最边上的两段。 维护一个单调栈栈中为当前可见直线(按照斜率排序)。 当加入一条直线l时可以发现 如果l与栈顶直线l的交点p在 l入栈前与栈顶直线 的交点p的左侧那么l会覆盖l(直接用与第一条直线的交点好像也可以)。弹出l加入l。 如果p在p右侧则保留栈顶直线并将l入栈如果重合那么后加入的直线应该会覆盖l弹出l加入l。 在斜率符号改变时结果也是一样的。更新栈的过程应持续到p在p的右侧。 如果有多条直线斜率相同截距大的直线会覆盖截距小的直线。排序后过掉即可。 这有图. //1800kb 160ms
#include cstdio
#include cctype
#include algorithm
#define gc() getchar()
const int N5e45;int n,sk[N],top,Ans[N];
struct Line{int k,b,id;bool operator (const Line a)const{return ka.k?ba.b:ka.k;}
}l[N];inline int read()
{int now0,f1;register char cgc();for(;!isdigit(c);cgc()) if(c-) f-1;for(;isdigit(c);nownow*10c-0,cgc());return now*f;
}
bool Check(int a,int b,int c){//p(l_al_b) is on the left of p(l_bl_c)return 1ll*(l[a].b-l[b].b)*(l[c].k-l[b].k)1ll*(l[b].b-l[c].b)*(l[b].k-l[a].k);
}int main()
{nread();for(int i1; in; i) l[i].kread(),l[i].bread(),l[i].idi;std::sort(l1,l1n), sk[top1]1;for(int i2; in; i){if(l[i].kl[i-1].k) continue;while(top1 Check(i,sk[top],sk[top-1])) --top;//x(b2-b1)/(k1-k2)sk[top]i;}for(int i1; itop; i) Ans[i]l[sk[i]].id;std::sort(Ans1,Ans1top);for(int i1; itop; i) printf(%d ,Ans[i]);return 0;
} 转载于:https://www.cnblogs.com/SovietPower/p/8758159.html
