bzoj1007--水準可見直線

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn=5*1e4+1000;
const double eps=1e-8;

struct Node{
  
  double a,b;
  int id;
}node[maxn],stack[maxn]; 
bool isok[maxn];
int top;

bool cmp(Node A,Node B){
  
  if(fabs(A.a-B.a)<eps) return A.b<B.b; 
  return A.a<B.a;
}

double getX(Node A,Node B){
  
  return (A.b-B.b)/(B.a-A.a);
}

int main(){
  
  int n;
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    
    scanf("%lf%lf",&node[i].a,&node[i].b);
    node[i].id=i;
    isok[i]=false;
  }
  sort(node,node+n,cmp);
  for(int i=0;i<n;i++){
    
    while(top){
      
      if(fabs(stack[top].a-node[i].a)<eps) top--;
        else if(top>1&&getX(node[i],stack[top-1])<=getX(stack[top],stack[top-1])) top--;
        else break;
    }
    stack[++top]=node[i]; 
  }
  for(int i=1;i<=top;i++) isok[stack[i].id]=true;
  for(int i=0;i<n;i++) if(isok[i]) printf("%d ",i+1);
}