恩

差点直接交上去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过不了

数据未修复，请写题的人把不存在的边边权设成1e9+1。

差分真好玩

一个弗洛伊德我w了2次.....

还是不很懂啊.....

数据错的就不能怪我特判了→_→居然还是rk1

当年考试时推了我一个来小时的方程
本以为A了
然后= =
10分2333

回复 @Hallmeow :
2333

回复 @沉迷学习的假��Keller :
6666

为什么输入可以有1