题解:#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 1E5+10;
const double eps = 1e-9;
int n,m,tmp[N],ke[N],pn;
double pk[N],ans[N];
int ask[N][2];
struct Point{Point(double a=0,double b=0):x(a),y(b){}double x,y;}data[N];
Point operator-(const Point&a,const Point&b){return Point(a.x-b.x,a.y-b.y);}
double Cross(Point a,Point b){return a.x*b.y-a.y*b.x;}
double calck(Point a,Point b){return 1.*(b.y-a.y)/(b.x-a.x);}
double calcm(Point a,double k){return -k*a.x + a.y;}
bool better(Point a,Point b,Point c){return Cross(a-b,b-c)>=0;}
bool dcmp(double a,double b){return fabs(a-b)<=eps;}
bool pcmp(int A,int B){
Point &a=data[A],&b=data[B];
return dcmp(a.x,b.x)?a.y>b.y:a.x<b.x;
}
bool cmpk(double a,double b){return a>b;}
deque<int>dui;
int solve(int l=1,int r=n){
if(l==r){
if(ask[l][0] == 0)return 0;
ke[l]=ask[l][1];
pk[l]=1e50;
return 1;
}
int mid = (l+r)/2,len[2],i,j,re=0;
len[0] = solve(l,mid);len[1] = solve(mid+1,r);
for(i=mid+1;i<=r;i++)
if(ask[i][0]==0){
j = lower_bound(pk+l,pk+l+len[0],1-ask[i][1],cmpk)-pk-1;
double atmp=calcm(data[ke[j]],1-ask[i][1]);
if(atmp > ans[i])ans[i] = atmp;
}
//merge
merge(ke+l,ke+l+len[0],ke+(mid+1),ke+(mid+1)+len[1],tmp+1,pcmp);
for(i=1;i<=len[0]+len[1];i++)
if(i==1||dcmp(data[tmp[i]].x,data[tmp[i-1]].x)==0){
int now = tmp[i];
while((j=dui.size())>1 && better(data[dui[j-2]],data[dui[j-1]],data[now]))dui.pop_back();
dui.push_back(now);
}
while(!dui.empty()){
int p = (++re)+l-1;
ke[p] = dui.front();dui.pop_front();
if(re-1>=1)pk[p] = calck(data[ke[p-1]],data[ke[p]]);
else pk[p] = 1e50;
}
return re;
}
int main(){
int i,j,a;char opt[20];
double fa,fb;
scanf("%d",&n);
for(i=1;i<=n;i++){
scanf("%s",opt+1);
switch(opt[1]){
case'Q':
scanf("%d",&a);
ask[i][0] = 0;ask[i][1] = a;
break;
case'P':
scanf("%lf%lf",&fa,&fb);
data[++pn] = Point(fb,fa);
ask[i][0] = 1;ask[i][1] = pn;
break;
}
}
solve();
for(i=1;i<=n;i++)
if(ask[i][0]==0){
printf("%d\n",(int)((ans[i]+eps)/100));
}
return 0;
}
评论