题目大意
在平面直角坐标系中，Wayne需要你完成$n$次操作，操作只有两种：
$1.\,0\,x\,y$。表示在坐标系中加入一个以$(x, y)$为圆心且过原点的圆。
$2.\,1\,x\,y$。表示询问点$(x, y)$是否在所有已加入的圆的内部（含圆周），且至少在一个圆内部（含圆周）。
为了减少你的工作量，题目保证圆心严格在$x$轴上方（纵坐标为正），且横坐标非零。
强制在线。
题目分析
因为强制在线，我们没法用cdq分治解决本题。
使用论文上的方法：二进制分组。
类似$2048$游戏的规则，我们每加入一个修改点，将其建成一个大小为$1$的块，检查与前面的块的关系。
- 若与前一个块大小相等，将前一个块与当前块合并。
- 若与前一个块大小不等，维护新块中的凸包信息。
举例，若我们有$6$个修改点（数字代表修改点的编号），此时块的关系如下：
若我们加入第$7$个修改点，直接新建一个块：
若加入第$8$个修改点，先新建一个块：
发现最后两个块大小相等，合并：
发现最后两个块大小相等，合并：
发现最后两个块大小相等，合并：
此时仅有一个块，结束合并，重建新块中的凸包。
对于询问，我们在每个点中都询问一次，最后合并起来（取交）即为答案，具体细节后面再说，先考虑时间复杂度。
时间复杂度
不难发现，在添加第$k$个修改点的时候，我们会重建$lowbit(k)$个修改点将其合并成一个块。
设$f(i)$表示将长度为$i$的块重建所消耗的时间。
因此所有的插入造成的时间总和为$O(f(n)\log n)$。
实现与细节
我们要维护两个凸包，但根据半平面的方向，可以判断出使用上凸包还是下凸包。
令半平面$2x_0x+2y_0y\ge x_0^2+y_0^2$的$(x,y)$取$(0,0)$，得$x_0^2+y_0^2\le0$，恒不成立（忽略等号），故半平面始终不包含$(0,0)$。
移项得$2y_0y\ge -2x_0x+x_0^2+y_0^2$，故截距的正负取决于$y_0$的正负，因此当$y_0\lt 0$，截距小于零，半平面包含下半部分，求上凸包；截距大于零类似。
在询问的时候，如果直接对斜率进行二分，可能会出现半平面斜率不存在的情况，此时我们考虑使用点积二分找到临界点。
如何通过点积判断临界点。
代数法（by 红太阳xyj）
以上凸包举例：
如图，设凸包上一条红色斜率为$\frac{\delta y}{\delta x}$，半平面斜率为$-\frac{x_0}{y_0}$，故此时有：
分子部分是点积形式，此时$\delta x\gt 0,y_0\lt 0$，因此点积小于$0$时说明左端点应该向中间移动，否则移动右端点。
几何法（by Bill_Yang）
如图，蓝色的为半平面，绿色的为$(x_0,y_0)$向量，向量与半平面垂直。
如图，当点积变号时一定经过所求的端点。
如图，当点积$\lt 0$时说明左端点应该向中间移动，否则移动右端点。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const double eps=1e-8;
const int maxn=500005;
int dcmp(double x) {
if(fabs(x)<eps)return 0;
return x>eps?1:-1;
}
struct Point {
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y) {}
Point operator - (const Point& b) {
return Point(b.x-x,b.y-y);
}
bool operator < (const Point& b) const {
return dcmp(x-b.x)<0||(dcmp(x-b.x)==0&&y<b.y);
}
} p[maxn];
typedef Point Vector;
double Cross(Vector a,Vector b) {
return a.x*b.y-b.x*a.y;
}
double Dot(Vector a,Vector b) {
return a.x*b.x+a.y*b.y;
}
struct Group {
int Left,Right,size;
vector<Point>Up,Down;
Group(int l=0,int r=0):Left(l),Right(r),size(r-l+1) {
Up=Down=vector<Point>();
}
void Scan() {
for(int i=Right; i>=Left; i--) {
while(Down.size()>=2&&dcmp(Cross(Down[Down.size()-2]-Down.back(),Down[Down.size()-2]-p[i]))>=0)Down.pop_back();
Down.push_back(p[i]);
}
for(int i=Left; i<=Right; i++) {
while(Up.size()>=2&&dcmp(Cross(Up[Up.size()-2]-Up.back(),Up[Up.size()-2]-p[i]))>=0)Up.pop_back();
Up.push_back(p[i]);
}
if(!Up.empty())Up.push_back(Point(Up.back().x+eps,-INT_MAX));
if(!Down.empty())Down.push_back(Point(Down.back().x-eps,INT_MAX));
}
void build() {
sort(p+Left,p+Right+1);
Up.clear();
Down.clear();
Scan();
}
bool query(Point q) {
Point ans;
if(q.y<0) {
int left=0,right=Up.size()-2;
while(left<=right) {
int mid=(left+right)>>1;
if(dcmp(Dot(Up[mid]-Up[mid+1],q))>=0)right=mid-1;
else left=mid+1;
}
ans=Up[left];
} else {
int left=0,right=Down.size()-2;
while(left<=right) {
int mid=(left+right)>>1;
if(dcmp(Dot(Down[mid+1]-Down[mid],q))<=0)right=mid-1;
else left=mid+1;
}
ans=Down[left];
}
return dcmp(2*q.x*ans.x+2*q.y*ans.y-(q.x*q.x+q.y*q.y))>=0;
}
};
vector<Group>G;
int n=0,tot=0;
void insert(Point New) {
p[++n]=New;
G.push_back(Group(n,n));
while(G.size()>=2&&G.back().size==G[G.size()-2].size) {
G.pop_back();
G.back()=Group(G.back().Left,n);
}
G.back().build();
}
bool query(Point q) {
if(!n)return 0;
bool flag=1;
for(auto& g:G) {
flag=g.query(q);
if(!flag)break;
}
if(flag)tot++;
return flag;
}
int main() {
int t=Get_Int();
for(int i=1; i<=t; i++) {
int opt=Get_Int();
double x,y;
scanf("%lf%lf",&x,&y);
x+=tot,y+=tot;
if(!opt)insert(Point(x,y));
else puts(query(Point(x,y))?"Yes":"No");
}
return 0;
}
|
