点击这里查看原题
最终得到的一定是一个下凸壳，因此把所有直线以k升序为第一关键字，b降序为第二关键字进行排序。若当前直线能完全覆盖栈顶直线，即i与s[top]的交点在s[top]与s[top-1]的交点左侧，则将栈顶元素弹出。
/*
User:Small
Language:C++
Problem No.:1007
*/
#include<bits/stdc++.h>
#define ll long long
#define inf 999999999
using namespace std;
const int M=1e6+5;
int n,s[M],tp;
bool ans[M];
struct no{
double k,b;
int id;
bool operator<(const no y)const{
return k==y.k?b>y.b:k<y.k;
}
}l[M];
double getpos(no x,no y){
return (y.b-x.b)/(x.k-y.k);
}
int main(){
freopen("data.in","r",stdin);//
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%lf%lf",&l[i].k,&l[i].b);
l[i].id=i;
}
sort(l+1,l+n+1);
s[++tp]=1;
for(int i=2;i<=n;i++){
if(l[i].k-l[i-1].k<1e-8) continue;
while(tp>1&&getpos(l[i],l[s[tp]])<=getpos(l[s[tp]],l[s[tp-1]])) tp--;
s[++tp]=i;
}
for(int i=1;i<=tp;i++) ans[l[s[i]].id]=1;
for(int i=1;i<=n;i++) if(ans[i]) printf("%d ",i);
return 0;
}