IOI2020集训队作业

随便做做。

[CF549 E]

solution

题面:给定平面上两组整点,分别有 $n,m$ 个,坐标范围在 $[-R,R]$ 之间,问是否存在一个圆,满足其中一组点均在圆内 (含边界),另外一组点均在圆外 (不含边界)。

做法:先考虑一个做法,我们强行找到每个包含一组点的圆(显然经过两点更不劣),判断另一组点是否在其外。这样显然存在一个问题,我们不太好枚举所有包含一组点的圆,直接暴力复杂度不符合要求。

回忆起 [ZJOI2018]保镖,我们将平面一个点 $(x,y)$ 映射到 $z=x^2+y^2$ 的抛物面后,对一组点求出三维凸包,我们可以证明上凸包的平面与支配圆一一映射(定义支配圆为包含一组点的圆)。这个性质的证明如下:

我们先写出平面的圆方程: $x^2+y^2+Dx+Ey+F=z+Dx+Ey+F=0$,将 $(x,y,z)$ 看作空间里的一个点后,圆方程就可以被看成一个平面。因此,一个点在圆内外等价于这个点的映射在平面的哪一侧。

于是,一个支配圆意味着所有的点的映射都在这个支配圆的映射平面的内侧。因此,求出三维凸包后,上凸包的内侧就是指在上凸包里面。也即上凸包的每一个平面都对应一个支配圆,每一个支配圆都对应一个上凸包上的平面。

为了确保唯一性,我们对所有点做一个微小扰动,使得平面上没有四个点是共圆的,保证了唯一性。

这样我们得到了一个比较优秀的做法,求出三维凸包后,枚举上凸包的每一个平面,看看是否隔断两组点。但由于三维凸包的 $O(n\log n)$ 做法比较复杂,我们重新想回二维。

我们重新将上凸包投射到二维空间里,我们可以称其为支配三角剖分Anti-Delaunay Triagulation。这个三角剖分满足每个三角形的外接圆包含一组点,而且我们知道这样的三角形个数是 $O(convex(n))$ 级别的。($convex(n)$ 表示凸包上的点数)

现在的关键就是求出这个三角剖分,我们考虑分治。开始先枚举一条边,然后找到唯一确定的支配三角形(唯一性上面已经证明),然后按着三角形的剩下两条边切开多边形,继续分治下去。由于它映射到空间的三维凸包是惟一的,所以这样的分治也是惟一且正确的。

于是总复杂度就是 $O(convex(n)(n+m)+n\log n+m\log m)$。

而 $O(convex(n))=O(R^\frac{2}{3})$,于是我们就做完了这道题。

具体实现上学习了鱼大的做法,计算弧度来避免使用开方等操作而减少了精度。

code
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
//2021.7.19 by ljz
//email 573902690@qq.com
//if you find any bug in my code
//please tell me
const int N=1e4+10;
namespace MAIN{
inline db Rand(){
return 1.0*rand()/RAND_MAX;
}
inline db Reps(){
return 0;
// return (Rand()-0.5)*eps;
}
struct P{
db x,y;
P() {}
P(db x,db y):x(x),y(y) {}
inline void r(){
cin>>x>>y,x+=Reps(),y+=Reps();
}
inline bool operator < (const RG P &B) const{
return x<B.x||(x==B.x&&y<B.y);
}
inline db operator ^ (const RG P &B)const{
return x*B.y-y*B.x;
}
inline db operator * (const RG P &B)const{
return x*B.x+y*B.y;
}
inline bool operator << (const RG P &B)const{
return (y<0)^(B.y<0)?B.y<0:(*this^B)>0||((*this^B)==0&&x>=0&&B.x<0);
}
inline P operator - () const{
return P(-x,-y);
}
}a[N],b[N],c[N];
inline db len(const P &a){
return sqrt(a.x*a.x+a.y*a.y);
}
inline P operator + (const P &a,const P &b){
return P(a.x+b.x,a.y+b.y);
}
inline P operator - (const P &a,const P &b){
return P(a.x-b.x,a.y-b.y);
}
inline bool cmp(const P &a,const P &b){
return (a^b)!=0?(a^b)>0:len(a)<len(b);
}
inline db dot(const RG P &x,const RG P &y,const RG P &z){
return (((y)-(x))*((z)-(x)));
}
inline db crs(const RG P &x,const RG P &y,const RG P &z){
return (((y)-(x))^((z)-(x)));
}
inline P angle(const RG P &x,const RG P &y,const RG P &z){
return P(dot(x,y,z),crs(x,y,z));
}
inline int graham(res n,RG P *A,RG P *B){
static int st[N];
res top=0;
sort(A+1,A+n+1);
RG P o=A[1];
for(res i=n;i;i--)A[i]=A[i]-o;
sort(A+2,A+n+1,cmp);
for(res i=1;i<=n;st[++top]=i,i++)while(top>=2&&((A[i]-A[st[top-1]])^(A[st[top]]-A[st[top-1]]))>=0)top--;
for(res i=1;i<=top;i++)B[i]=A[st[i]]+o;
for(res i=1;i<=n;i++)A[i]=A[i]+o;
return top;
}
inline int up(RG P &x,const RG P y){
return x<<y?x=y,1:0;
}
inline int down(RG P &x,const RG P y){
return y<<x?x=y,1:0;
}
int convex;
bool ck(res L,res R,const RG P *ch,const res &n){
P mn(1,0),mx(inf,-1);
res p=0;
for(res i=L+1;i<R;i++)if(up(mn,angle(c[i],c[L],c[R])))p=i;
for(res i=R+1;i!=L;i++){
if(i==convex+1)i=1;
if(i==L||i==R)break;
down(mx,-angle(c[i],c[L],c[R]));
}
res fl=1;
for(res i=1;i<=n;i++){
RG P o=angle(ch[i],c[L],c[R]);
if(!o.y){if(o.x<=0){fl=0;break;}}
else if(o.y<0)down(mx,o);
else up(mn,-o);
if(!(mn<<mx)){fl=0;break;}
}
return fl||(p&&(ck(L,p,ch,n)||ck(p,R,ch,n)));
}
inline void MAIN(){
res n=read(),m=read();
for(res i=1;i<=n;i++)a[i].r();
for(res i=1;i<=m;i++)b[i].r();
convex=graham(n,a,c);
if(convex==1||ck(1,convex,b,m)){puts("YES");return;}
convex=graham(m,b,c);
if(convex==1||ck(1,convex,a,n)){puts("YES");return;}
puts("NO");
}
}