BZOJ 1007(水平可见直线-斜率排序+栈贪心)

#include
#include
#include
#include
#include
#include
using namespace std;
#define MAXN (50000+10)
int n;
struct line
{
  int k,b,i;
  friend bool operator<(line a,line b) {return (a.k==b.k)?a.b>b.b:a.k<b.k;  }
  friend double intx(line a,line b)
  {
    return (double)(b.b-a.b)/(a.k-b.k);
  }
}a[MAXN];
int s[MAXN],size=0;
void push(int x)
{
  while (size>1&&intx(a[s[size]],a[s[size-1]])>=intx(a[s[size]],a[x])) size--;
  s[++size]=x;  
}
bool b[MAXN];
int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++) {scanf("%d%d",&a[i].k,&a[i].b);a[i].i=i;}
  sort(a+1,a+1+n);
  push(1);
  for (int i=2;i<=n;i++)
    if (a[i].k>a[i-1].k) push(i);
//  for (int i=1;)
  memset(b,0,sizeof(b));for (int i=1;i<=size;i++) b[a[s[i]].i]=1;
  for (int i=1;i<=n;i++) if (b[i]) cout<<i<<' ';
  return 0;
}