乱搜= =

回复 @冰可乐w :
日常写水题降低正确率，数组不小心开爆了23333

二维偏序，cdq分治.

盖楼盖楼

priority_queue，STL大法好

加了氧气还慢一些是为什么

不加快读0.003秒求虐

同被0坑了一下

把167代码粘上去不对，然后参照大神的代码奇奇怪怪的改了几个奇奇怪怪的地方就奇奇怪怪的过了

这是逼我全用longlong........

恩

差点直接交上去01背包。。
真是奇技淫巧题，是在下输了。

日常水题

数据范圈是什么鬼。

#include<bits/stdc++.h>
#define RG register
#define il inline
#define N 50010
#define db double
using namespace std;
struct point{
db x,y;
point() {}
point(db _x,db _y):x(_x),y(_y) {}
point operator + (const point & a)const{return point(x+a.x,y+a.y);}
point operator - (const point & a)const{return point(x-a.x,y-a.y);}
point operator * (const db k)const{return point (k*x,k*y);}
db operator * (const point & a){return x*a.y-y*a.x;}
};
struct line{
db k,b;int id;
line() {}
line(db K,db B,int I):k(K),b(B),id(I) {}
}l[N];
int que[N];
bool comp(const line & a,const line & b){return a.k<b.k;}
int n,ans[N];
bool check(line l1,line l2,line l0){
db k1=l1.k,b1=l1.b,k2=l2.k,b2=l2.b;
db k3=l0.k,b3=l0.b;db kk,bb,kkk,bbb;
if(k1-k2<0)kk=k2-k1,bb=b1-b2;else kk=k1-k2,bb=b2-b1;
if(k3-k2<0)kkk=k2-k3,bbb=b3-b2;else kkk=k3-k2,bbb=b2-b3;
return bb*kkk>bbb*kk;
}
int main(){
freopen("bzoj_1007.in","r",stdin);
freopen("bzoj_1007.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;++i){
db k,b;scanf("%lf%lf",&k,&b);
l[i]=line(k,b,i);
}sort(l+1,l+n+1,comp);int top=2;
que[1]=1,que[2]=2;
for(int i=3;i<=n;++i){
while(top>=2&&check(l[que[top-1]],l[que[top]],l[i]))top--;
que[++top]=i;
}if(n==1)cout<<1<<" ",exit(0);
for(int i=1;i<=top;++i)ans[++ans[0]]=l[que[i]].id;
sort(ans+1,ans+ans[0]+1);
for(int i=1;i<=ans[0];++i)printf("%d ",ans[i]);
return 0;
}

最后一个点打表了，很惭愧

把排序工作量代码交上去都能过

分块时 块长为定值不一定跑得永远最快
1000 6s
sqrt（n） 3s
...

坑人[b]的数据读入，cin.eof()在linux下多读了一个字符，导致读入的导弹数比实际的多1，不写n--评测机过不了，写了本地windows过不了