参考了这篇博客 http://blog.csdn.net/u013912596/article/details/47978791
我的做法：
其实每次询问就是 找一个向量(x,y)使得 （x,y)*(p,q)最大。根据向量点积的性质很容易发现最优的向量肯定在凸包上。
如果没有删除操作，可以用平衡树来维护上凸壳和下凸壳，每次询问二分查找。
这题有删除操作，看了题解再想了很久才知道怎么分治。
对于一个操作区间【L,R】：
如果【L,mid】区间内的添加的向量在 R 之后被删除或者不删，那么就可以用它们构建上下凸壳来更新【mid+1,R】区间内的询问。
如果【mid+1，R】区间内的删除的向量在 L 之前添加，那么也可以用它们构建上下凸壳来更新【L,mid】区间内的询问。
然后就做完了。
一些小技巧：下凸壳可以翻转一下变成上凸壳用同样的方法维护，nxt数组记录与操作i相关的另一个操作的位置，可以很方便的判断它是添加操作还是删除操作。
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=50005;
const ll INF=0x3f3f3f3f3f3f3f3fll;
int n;
ll ans[N];
int nxt[N];
struct P
{
int x,y;
bool operator<(const P &t)const
{
return x<t.x||x==t.x&&y>t.y;
}
P operator-(const P &t)
{
return {x-t.x,y-t.y};
}
ll operator*(const P &t)
{
return 1ll*x*t.x+1ll*y*t.y;
}
ll operator^(const P &t)
{
return 1ll*x*t.y-1ll*y*t.x;
}
}a[N];
ll cross(P a,P b,P c)
{
return (b-a)^(c-b);
}
map<P,int>mp;
struct hull
{
int n,top;
P a[N],stk[N];
void init()
{
n=0;
}
void add(P p)
{
a[++n]=p;
}
void make()
{
sort(a+1,a+n+1);
top=0;
for (int i=1;i<=n;i++)
{
while(top>1&&cross(stk[top-1],stk[top],a[i])>=0) top--;
stk[++top]=a[i];
}
}
ll get(P p)
{
if (top==0) return -INF;
int l=1,r=top;
while(l<r)
{
int mid=(l+r)/2;
if (p*stk[mid]<p*stk[mid+1]) l=mid+1;else r=mid;
}
return p*stk[l];
}
}up,down;
void solve(int l,int r)
{
if (l==r) return;
int mid=(l+r)/2;
up.init(); down.init();
for (int i=l;i<=mid;i++)
if (nxt[i]>r)
{
up.add(a[i]);
down.add({a[i].x,-a[i].y});
}
up.make(); down.make();
for (int i=mid+1;i<=r;i++)
if (nxt[i]==i)
{
ans[i]=max(ans[i],up.get(a[i])),
ans[i]=max(ans[i],down.get({a[i].x,-a[i].y}));
}
up.init(); down.init();
for (int i=mid+1;i<=r;i++)
if (nxt[i]<l)
{
up.add(a[i]);
down.add({a[i].x,-a[i].y});
}
up.make(); down.make();
for (int i=l;i<=mid;i++)
if (nxt[i]==i)
{
ans[i]=max(ans[i],up.get(a[i]));
ans[i]=max(ans[i],down.get({a[i].x,-a[i].y}));
}
solve(l,mid);
solve(mid+1,r);
}
int main()
{
while(scanf("%d",&n),n)
{
mp.clear();
for (int i=1;i<=n;i++) ans[i]=-INF;
for (int i=1;i<=n;i++)
{
int tp;
scanf("%d%d%d",&tp,&a[i].x,&a[i].y);
if (tp==1) nxt[i]=n+1,mp[a[i]]=i;
if (tp==-1)
{
int id=mp[a[i]];
nxt[id]=i; nxt[i]=id;
mp.erase(a[i]);
}
if (tp==0) nxt[i]=i;
}
solve(1,n);
for (int i=1;i<=n;i++)
if (nxt[i]==i) printf("%lld\n",ans[i]);
}
}
