题意：
动态加入过原点的圆，询问一个点是否在所有圆内或圆上。加强版要强制在线。
题解：
设第$i$个圆$C_i$的方程为$(x - x_i) ^ 2 + (y - y_i) ^ 2 = x_i ^ 2 + y_i ^ 2$，则点$P(x_0, y_0)$要在$\odot C_i$中，就要满足$$
(x_0 - x_i) ^ 2 + (y_0 - y_i) ^ 2 \le x_i ^ 2 + y_i ^ 2 \\\
x_0 ^ 2 + y_0 ^ 2 \le 2 (x_0 x_i + y_0 y_i)
x_0 ^ 2 + y_0 ^ 2 \le 2 \min \lbrace x_0 x_i + y_0 y_i \rbrace
$$
设$z = x_0 x_i + y_0 y_i$，则$y_i = -\frac{x_0}{y_0} + \frac z {y_0}$。$z$取最小值时，$(x_i, y_i)$一定在下凸包上，用splay维护一下就好了。
代码：
强制在线版
#include <bits/stdc++.h>
using namespace std;
int n, cnt = 0;
const double eps = 1e-12, inf = 1e40;
struct pnt
{
double x, y;
pnt() {}
pnt(double x, double y) : x(x), y(y) {}
};
pnt operator+(pnt x, pnt y) { return pnt(x.x + y.x, x.y + y.y); }
pnt operator-(pnt x, pnt y) { return pnt(x.x - y.x, x.y - y.y); }
double operator*(pnt x, pnt y) { return x.x * y.y - x.y * y.x; }
struct tree
{
pnt x;
double k;
tree *f, *s[2];
tree(pnt x) : x(x), f(NULL), s() {}
} *root;
double get_k(pnt x, pnt y) { return (y.y - x.y) / (y.x - x.x); }
void rot(tree *x)
{
tree *f = x->f, *ff = f->f;
int w = x == f->s[0];
f->s[w ^ 1] = x->s[w];
if (x->s[w]) x->s[w]->f = f;
if (ff) ff->s[f == ff->s[1]] = x;
x->f = ff;
x->s[w] = f;
f->f = x;
}
void splay(tree *x, tree *rt)
{
while (x->f != rt)
{
tree *f = x->f, *ff = f->f;
if (ff == rt) rot(x);
else if ((x == f->s[0]) == (f == ff->s[0])) rot(f), rot(x);
else rot(x), rot(x);
}
if (!rt) root = x;
}
tree *fd(pnt x)
{
tree *p = root, *f;
while (p)
{
f = p;
if (x.x + eps < p->x.x) p = p->s[0];
else if (x.x - eps > p->x.x) p = p->s[1];
else return p;
}
return f;
}
tree *pre(tree *x)
{
if (!x) return x;
splay(x, 0);
x = x->s[0];
if (!x) return x;
while (x->s[1]) x = x->s[1];
return x;
}
tree *nxt(tree *x)
{
if (!x) return x;
splay(x, 0);
x = x->s[1];
if (!x) return x;
while (x->s[0]) x = x->s[0];
return x;
}
void erase(tree *x)
{
splay(x, 0);
if (!x->s[0] && !x->s[1]) root = NULL;
else if (!x->s[0] && x->s[1]) root = x->s[1], x->s[1]->f = NULL, x->s[1]->k = -inf;
else if (x->s[0] && !x->s[1]) root = x->s[0], x->s[0]->f = NULL;
else
{
tree *hh = x->s[0];
while (hh->s[1]) hh = hh->s[1];
splay(hh, x);
hh->s[1] = x->s[1];
x->s[1]->f = hh;
hh->f = NULL;
root = hh;
tree *oo = nxt(root);
splay(oo, root);
oo->k = get_k(root->x, oo->x);
}
delete x;
}
void insert(pnt x)
{
if (!root)
{
root = new tree(x);
root->k = -inf;
}
else
{
tree *p = fd(x);
if (abs(p->x.x - x.x) < eps)
{
if (x.y > p->x.y + eps) return;
p->x = x;
}
else if (x.x > p->x.x)
{
p->s[1] = new tree(x);
p->s[1]->f = p;
p = p->s[1];
}
else
{
p->s[0] = new tree(x);
p->s[0]->f = p;
p = p->s[0];
}
splay(p, 0);
tree *l = pre(p), *r = nxt(p);
// if (l) printf("l: (%lf, %lf) %lf\n", l->x.x, l->x.y, l->k);
// if (r) printf("r: (%lf, %lf) %lf\n", r->x.x, r->x.y, r->k);
if (l && r && (r->x - l->x) * (p->x - l->x) > eps)
{
// puts("a");
erase(p);
return;
}
tree *l1 = pre(p), *l2 = pre(l1);
while (l2)
{
if ((x - l2->x) * (l1->x - l2->x) > eps) erase(l1);
l1 = l2;
l2 = pre(l2);
}
tree *r1 = nxt(p), *r2 = nxt(r1);
while (r2)
{
if ((r2->x - x) * (r1->x - x) > eps) erase(r1);
r1 = r2;
r2 = nxt(r2);
}
l = pre(p), r = nxt(p);
if (l) p->k = get_k(p->x, l->x); else p->k = -inf;
if (r) r->k = get_k(r->x, p->x);
}
}
tree *fd(double x)
{
tree *p = root, *f = NULL;
while (p)
{
f = p;
if (x + eps < p->k) p = p->s[0];
else if (x - eps > p->k) p = p->s[1];
else return p;
}
p = f;
if (p && p->k > x) p = pre(p);
return p;
}
void print(tree *x)
{
if (!x) return;
print(x->s[0]);
printf("(%lf, %lf) %lf\n", x->x.x, x->x.y, x->k);
print(x->s[1]);
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
int op;
double x, y;
scanf("%d%lf%lf", &op, &x, &y);
x += cnt;
y += cnt;
if (op == 0) insert(pnt(x, y));
else
{
tree *p = fd(-x / y);
// printf("(%lf, %lf)\n", p->x.x, p->x.y);
puts(p && x * x + y * y <= 2 * (x * p->x.x + y * p->x.y) ? (cnt++, "Yes") : "No");
}
// print(root);
}
}