需要在一个凸包 S 上二分出第一个位置 x,使得 Slope(Sx−1,Sx)>=k。
正确写法:
int query(double k){
int l=1,r=top;
while(l<r){
int mid=(l+r+1)>>1;
if(K(sta[mid-1],sta[mid])>=k) l=mid;
else r=mid-1;
}
return sta[l];
}
错误写法:
int query(double k){
int l=1,r=top;
while(l<=r){
int mid=(l+r)>>1;
if(K(sta[mid-1],sta[mid])>=k) l=mid+1;
else r=mid-1;
}
return sta[r];
}
求指正。