/************************************************************** Problem: 1007 User: lxy8584099 Language: C++ Result: Accepted Time:348 ms Memory:2192 kb ****************************************************************/ /* 入栈出栈的过程 有点像凸包? 按斜率从小到大排序(第二关键字耶从小到大) 遍历他们就像是一条线逆时针旋转。。 如果改线与top的交点在 和 top-1与top 的交点的左边 top-- 原因是因为改线一定能吧top可见部分覆盖完 画图可证 有相同斜率也要出栈 因为第二关键字也从小到大排序 fabs一定不要手写。。 */ #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N=5e4+50; const double esp=1e-9; struct xian {double k,b;int p;} e[N]; bool cmp(xian a,xian b) { if(fabs(a.k-b.k)<esp) return a.b<b.b; return a.k<b.k; } int n,sta[N],top,vis[N]; double calex(int i,int j) { double k1=e[i].k,k2=e[j].k; double b1=e[i].b,b2=e[j].b; double res=(b2-b1)/(k1-k2); // printf("%d %d : %lf\n",i,j,res); return res; } int main() { scanf("%d",&n) ; for(int i=1;i<=n;i++) scanf("%lf%lf",&e[i].k,&e[i].b),e[i].p=i; sort(e+1,e+n+1,cmp); // for(int i=1;i<=n;i++) // printf("%lf %lf\n",e[i].k,e[i].b); for(int i=1;i<=n;i++) { while(top) { if(fabs(e[i].k-e[sta[top]].k)<esp) top--; else if(top>1&&calex(i,sta[top-1])<=calex(sta[top],sta[top-1])) top--; else break; } sta[++top]=i; } for(int i=1;i<=top;i++) vis[e[sta[i]].p]=1; for(int i=1;i<=n;i++) if(vis[i]) printf("%d ",i); return 0; }

京公网安备 11010502036488号