题解
我们可以根据点积的定义，垂直于原点到给定点构成的直线作一条直线，从正无穷往下平移，第一个碰到的点就是答案
像什么，上凸壳哇
可是……动态维护上凸壳？
我们可以离线，计算每个点能造成贡献的一个询问区间[l,r]表示这个点在第l个询问和第r个询问之间存在，按照每个点的横坐标大小顺序插入线段树，我们就可以类似斜率优化构造出凸包
对于所有询问，我们可以给它们按极角排序，然后遍历线段树，如果按照极角排序，那么垂直于他们的直线斜率递减，最优点也右移
实现的方法就是一边遍历线段树，一边归并排序，每一层按照极角序遍历这个凸壳就好
代码
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>
//#define ivorysi
#define pb push_back
#define space putchar(' ')
#define enter putchar('\n')
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define mo 974711
#define MAXN 200005
#define RG register
using namespace std;
typedef long long int64;
typedef double db;
template<class T>
void read(T &res) {
res = 0;char c = getchar();T f = 1;
while(c < '0' || c > '9') {
if(c == '-') f = -1;
c = getchar();
}
while(c >= '0' && c <= '9') {
res = res * 10 + c - '0';
c = getchar();
}
res *= f;
}
template<class T>
void out(T x) {
if(x < 0) {putchar('-');x = -x;}
if(x >= 10) {
out(x / 10);
}
putchar('0' + x % 10);
}
struct Point {
int64 x,y;
Point(){}
Point(int64 _x,int64 _y) {
x = _x;y = _y;
}
friend Point operator + (const Point &a,const Point &b) {
return Point(a.x + b.x,a.y + b.y);
}
friend Point operator - (const Point &a,const Point &b) {
return Point(a.x - b.x,a.y - b.y);
}
friend int64 operator * (const Point &a,const Point &b) {
return a.x * b.y - a.y * b.x;
}
friend int64 dot(const Point &a,const Point &b) {
return a.x * b.x + a.y * b.y;
}
friend bool operator < (const Point &a,const Point &b) {
return a.x < b.x;
}
};
struct Inode {
Point a;int l,r;
friend bool operator < (const Inode &s,const Inode &t) {
return s.a < t.a;
}
}Ins[MAXN];
struct Qnode {
Point a;int id;
}Qry[MAXN],tmp[MAXN];
vector<Point> tr[MAXN * 4];
int N,cntI,cntQ,st[MAXN * 4];
int64 ans[MAXN];
void Insert(int u,int L,int R,int l,int r,Point a) {
if(L == l && R == r) {
int s = tr[u].size() - 1;
while(s > 0) {
if((tr[u][s] - tr[u][s - 1]) * (a - tr[u][s - 1]) >= 0) {
tr[u].pop_back();
}
else break;
--s;
}
tr[u].pb(a);
return ;
}
int mid = (L + R) >> 1;
if(r <= mid) Insert(u << 1,L,mid,l,r,a);
else if(l > mid) Insert(u << 1 | 1,mid + 1,R,l,r,a);
else {
Insert(u << 1,L,mid,l,mid,a);
Insert(u << 1 | 1,mid + 1,R,mid + 1,r,a);
}
}
void Init() {
read(N);
int t,id;int64 x,y;
for(int i = 1 ; i <= N ; ++i) {
read(t);
if(t == 1) {
read(x);read(y);
Ins[++cntI] = (Inode){Point(x,y),cntQ + 1,-1};
}
else if(t == 3) {
read(x);read(y);++cntQ;
Qry[cntQ] = (Qnode){Point(x,y),cntQ};
}
else {
read(id);
Ins[id].r = cntQ;
}
}
for(int i = 1 ; i <= cntI ; ++i) {
if(Ins[i].r == -1) Ins[i].r = cntQ;
}
sort(Ins + 1,Ins + cntI + 1);
for(int i = 1 ; i <= cntI ; ++i) {
if(Ins[i].l <= Ins[i].r) {
Insert(1,1,cntQ,Ins[i].l,Ins[i].r,Ins[i].a);
}
}
}
void Solve(int u,int L,int R) {
int mid = (L + R) >> 1;
if(L != R) {
Solve(u << 1,L,mid);Solve(u << 1 | 1,mid + 1,R);
int tl = L,tr = mid + 1,p = L;
while(tl <= mid && tr <= R) {
if(Qry[tr].a * Qry[tl].a >= 0) tmp[p++] = Qry[tl++];
else tmp[p++] = Qry[tr++];
}
while(tl <= mid) tmp[p++] = Qry[tl++];
while(tr <= R) tmp[p++] = Qry[tr++];
for(int i = L ; i <= R ; ++i) Qry[i] = tmp[i];
}
int s = tr[u].size() - 1;
if(s != -1) {
for(int i = L ; i <= R ; ++i) {
while(st[u] < s) {
if(dot(tr[u][st[u]],Qry[i].a) <= dot(tr[u][st[u] + 1],Qry[i].a)) {
++st[u];
}
else break;
}
ans[Qry[i].id] = max(ans[Qry[i].id],dot(Qry[i].a,tr[u][st[u]]));
}
}
}
int main() {
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
Init();
Solve(1,1,cntQ);
for(int i = 1 ; i <= cntQ ; ++i) out(ans[i]),enter;
return 0;
}