[HNOI2008]水平可见直线 单调栈

#include<cstdio>
#include<algorithm>
#include<string>
using namespace std;
void setIO(string a){
	freopen((a+".in").c_str(),"r",stdin);
}
const int maxn=100000+5;
struct Line{
	double slope, y;
}line[maxn];
int arr[maxn],ans[maxn],S[maxn],top;
bool cmp(int i,int j){
	if(line[i].slope==line[j].slope) return line[i].y>line[j].y;
	return line[i].slope<line[j].slope;
}
double get(int i,int j){
	return (line[i].y-line[j].y)/(line[j].slope-line[i].slope);
}
int main(){
	//setIO("input");
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;++i) {
		scanf("%lf%lf",&line[i].slope,&line[i].y);
		arr[i]=i;
	}
	sort(arr+1,arr+1+n,cmp);
    for(int i=1;i<=n;++i)
    {
    	int cur=arr[i];
  
    	if(line[cur].slope==line[arr[i-1]].slope && i!=1) continue;
    	while(top>1 && get(S[top],S[top-1])>=get(arr[i],S[top])) --top;
    	S[++top]=cur;
    	ans[top]=cur;
    }
    sort(ans+1,ans+1+top);
    for(int i=1;i<=top;++i) printf("%d ",ans[i]);
    return 0;
}