Computational Geometry

基本(2D)计算几何

点/向量的定义

struct Vec{
    db x,y; Vec(){} Vec(db _x, db _y){x=_x,y=_y;}
    inline Vec operator + (Vec b){return Vec(x+b.x,y+b.y);}
    inline Vec operator - (Vec b){return Vec(x-b.x,y-b.y);}
    inline Vec operator - (){return Vec(-x,-y);}
    inline db operator * (Vec b){return x*b.x+y*b.y;}
    inline db operator % (Vec b){return x*b.y-b.x*y;}
    inline db operator ~ (){return x*x+y*y;}
    inline bool operator ==(Vec b){return fabs(x-b.x) <= EPS && fabs(y-b.y) <= EPS;}
    inline bool operator !=(Vec b){return fabs(x-b.x) >  EPS || fabs(y-b.y) >  EPS;}
    inline Vec Unit(){static db _; return _ = sqrt(x*x+y*y), Vec( x/_,y/_);}
    inline Vec Norm(){static db _; return _ = sqrt(x*x+y*y), Vec(-y/_,x/_);}
    inline bool Quad(){return y > EPS || (fabs(y) <= EPS && x >= -EPS);}
    inline bool operator < (Vec b){return fabs(y-b.y) <= EPS ? x < b.x : y < b.y;}
};  typedef Vec Pt;
inline Vec operator / (Vec a, db k){return Vec(a.x/k,a.y/k);}
inline Vec operator * (db k, Vec a){return Vec(k*a.x,k*a.y);}
inline Vec operator * (Vec a, db k){return Vec(k*a.x,k*a.y);}
inline bool Para(Vec a, Vec b){return fabs(a%b) <= EPS;}
inline bool ToLeft(Vec a, Vec b){return b%a > EPS;}
inline void O(Pt a, char c = ' '){printf("(%.3f,%.3f)%c",a.x,a.y,c);}

点积和叉积似乎不太需要讲?

\begin{aligned} \vert a \times b \vert &= \vert a \vert \vert b \vert \vert \sin (a,b) \vert \\ a \cdot b &= \vert a \vert \vert b \vert \cos \langle a,b \rangle \\ \end{aligned}

向量旋转

\begin{bmatrix} \cos \theta & - \sin \theta \\ \sin \theta & \cos \theta \\ \end{bmatrix} \begin{bmatrix} x \\ y \\ \end{bmatrix} = \begin{bmatrix} x' \\ y' \\ \end{bmatrix}

直线/线段的定义

struct Line{
    Pt p[2]; Line(){} Line(Pt a, Pt b){p[0]=a,p[1]=b;}
    inline Pt& operator[](int i){return p[i];}
    inline Vec v(){return p[1]-p[0];}
};
inline bool cmpang(Vec a, Vec b){return a.Quad()^b.Quad() ? a.Quad() < b.Quad() : ToLeft(b,a);}
inline bool operator < (Line a, Line b){
    return Para(a.v(),b.v()) && a.v()*b.v() > EPS ? ToLeft(a[0]-b[0],b.v()) : cmpang(a.v(),b.v());
}

点斜式

两点式

假 · 直线相交

inline Pt Cross(Line a, Line b){
    static db _1, _2;
    _1 = (b[0]-a[0])%(b[1]-a[0]), _2 = (b[1]-a[1])%(b[0]-a[1]);
    return a[0]+_1/(_1+_2)*a.v();
}

真 · 直线相交

inline Pt Cross(Line a, Line b){
    return a[0]+(b.v()%(a[0]-b[0])/(a.v()%b.v()))*a.v();
}

多边形的定义

struct Poly{
    Pt p[MAXN+5]; int n;
    inline void clear(){n=0;}
    inline Pt& operator[](int i){return p[i];}
    inline Pt& back(){return p[n];}
    inline void push(Pt o){p[++n] = o;}
    inline void pop(){--n;}
    db Area(){
    	if(n<3) return 0; static db _; _ = 0;
        p[n+1] = p[1]; for(rint i = 1; i <= n; _ = _+p[i]%p[i+1], i++);
        return fabs(_)/2;
    }
};

注意多边形顶点必须逆时针序存放

假·凸多边形

多边形的定义

真·凸多边形

typedef vector<Pt> Poly;

注意多边形顶点必须逆时针序存放

基本(2D)解析几何

直线相交

\begin{aligned} y = k_1 x + b_1 \\ y = k_2 x + b_2 \\ \end{aligned} \\ x = \frac{b_2-b_1}{k_1-k_2} \\ y = k_1x + b_1 \\

任意曲线相交

联立求交点

关于直线的对称点

\begin{aligned} & (x,y) \\ \xrightarrow{Ax+By+C=0} & (x,y)-2d(\cos \theta, \sin \theta) \\ = & (x,y)-2\frac{Ax_0+By_0+C}{A^2+B^2}(A,B) \end{aligned}
d = \frac{Ax_0+By_0+C}{\sqrt{A^2+B^2}}

点到直线的有向距离

解析几何的基本结论

\frac{a}{\sin A} = \frac{b}{\sin B} = \frac{c}{\sin C} = 2r_{\text{circumcircle}}
\begin{aligned} a^2 &= b^2+c^2 - 2bc\cos A \\ b^2 &= a^2+c^2 - 2ac\cos B \\ c^2 &= a^2+b^2 - 2ab\cos C \\ \end{aligned}

正弦定理

余弦定理

解析几何的基本结论

海伦公式

\begin{aligned} & p \equiv \frac{1}{2}C_{\Delta ABC} = \frac{a+b+c}{2} \\ & S_{\Delta ABC} = \sqrt{p(p-a)(p-b)(p-c)} \end{aligned}

解析几何的基本结论

射影定理

\begin{aligned} CD^2 = AD \cdot BD \\ BC^2 = BD \cdot BA \\ AC^2 = AD \cdot AB \\ a = b \cos C + c \cos B \\ b = a \cos C + c \cos A \\ c = a \cos B + b \cos A \\ \end{aligned}

角度的计算

\cos \langle \vec a, \vec b \rangle = \frac{\vec a \cdot \vec b}{\vert \vec a \vert \vert \vec b \vert}
\cos A = \frac{b^2+c^2-a^2}{2bc}
atan2(y,x)
\in (-\pi,\pi]

Situation #Common Tangents
0
1
2
3
4
0 \le d \lt \vert r_1 - r_2 \vert
d = \vert r_1 - r_2 \vert
\vert r_1 - r_2 \vert \lt d \lt r_1+r_2
d = r_1+r_2
r_1+r_2 \lt d

进阶(2D)计算几何

角度的比较

inline bool Para(Vec a, Vec b){return fabs(a%b) <= EPS;}
inline bool ToLeft(Vec a, Vec b){return b%a > EPS;}

inline bool cmpang(Vec a, Vec b){return a.Quad()^b.Quad() ? a.Quad() < b.Quad() : ToLeft(b,a);}
inline bool operator < (Line a, Line b){
    return Para(a.v(),b.v()) && a.v()*b.v() > EPS ? ToLeft(a[0]-b[0],b.v()) : cmpang(a.v(),b.v());
}

Convex-Up

Concave-Up

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

求凸包

struct Vec{
    //...
    inline bool operator < (Vec b){return fabs(y-b.y) <= EPS ? x < b.x : y < b.y;}
};  typedef Vec Pt;

//      Unstrict      <==>      Strict 
//  !ToLeft(yyy,xxx)        ToLeft(xxx,yyy)

// (Unstrict) ConvexHull, return a CCW CH
// Pt on edge won't be considered part of the CH, uses function "cmpltl" and Pt "LTL"

Pt LTL; inline bool cmpltl(Pt a, Pt b){return Para(a=a-LTL,b=b-LTL) ? ~a < ~b : ToLeft(b,a);}
void CH(Pt p[], int m, Poly &R){
    R.clear(), LTL = *min_element(p+1,p+m+1), sort(p+1,p+m+1,cmpltl);
    for(rint i = 1; i <= m; R.push(p[i++]))
    	for(; R.n>1 && !ToLeft(p[i]-R[R.n-1],R[R.n]-R[R.n-1]); R.pop());
}

旋转卡壳

db RC(Poly &R, db Ans=0){
    for(rint i = (R[R.n+1] = R[1], 1), j = 2; i <= R.n; Ans = max(Ans,~(R[j]-R[i])), i++)
        for(; (R[i+1]-R[i])%(R[j]-R[i]) < (R[i+1]-R[i])%(R[j+1]-R[i]); j = j%R.n+1); return sqrt(Ans);
}

Minkowski和

// Notice that the indices are 0-based
void Minkowski(Poly &A, Poly &B, Poly &R){
    rint i = 0, j = 0; R.clear(), R.push_back(A[0]+B[0]);
    for(; ;){
        p = ToLeft(A[-~i%A.size()]-A[i],B[-~j%B.size()]-B[j]) ?
                A[i]+B[++j%=B.size()]
            :
                A[++i%=A.size()]+B[j];
        R.size()>1&&Para(p-R.back(),R.back()-R[R.size()-2]) ?
            R.pop_back(),0 : 0;
        R.push_back(p); if(!i&&!j) break;
    }   R.pop_back();
}

注意求Minkowski和之前要进行标准化

rotate(p+1,min_element(p+1,p+n+1),p+n+1);

另外,严格来说,求出的并非Minkowski和(其是一个有无限个点的集合),而是Minkowski和的凸包。

点与多边形位置关系

单组查询:可能为凹多边形

// Angle ∠AKB
inline db Angle(Pt A, Pt B, Pt K){
    static db _; B = B-K, A = A-K, _ = atan2(B.y,B.x)-atan2(A.y,A.x),
    _<=-PI-EPS?_+=2*PI:0, _>=PI+EPS?_-=2*PI:0; return _;
}
inline db SumAngle(Poly &R, Pt p){
    static db _; _ = 0;
    for(rint i = 0; i < R.size(); _ += Angle(R[i],R[-~i%n],p), i++);
    return _;
}
// ...


puts(fabs(SumAngle(R,p))>=EPS?"Yes":"No"));

点与多边形位置关系

// Pt on edge would be considered part of the CH

bool Q(Poly &E, Pt p){
    int _ = lower_bound(E.begin(),E.end()-1,p,cmpltl)-E.begin();
    return !ToLeft(E[_]-E[~-_],p-E[~-_]);
}

// ...

puts(LTL==p||(LTL<p&&Q(R,p))?"Yes":"No"));

多组查询

注意凸包结尾追加了LTL来避免边界情况

半平面交

inline bool cmpang(Vec a, Vec b){return a.Quad()^b.Quad() ? a.Quad() < b.Quad() : ToLeft(b,a);}
inline bool operator < (Line a, Line b){
    return Para(a.v(),b.v()) && a.v()*b.v() > EPS ? ToLeft(a[0]-b[0],b.v()) : cmpang(a.v(),b.v());
}

// ...

// (StrictLeft) HalfPlaneIntersection, return a CCW CH
// L[] should be sorted (with Line's operator < ) before passing in
void HPI(Line L[], int m, Poly &R){
    static Line q[MAXN+5]; static int head, tail; R.clear(), head = 1, q[tail=1] = L[1];
    for(rint i = 2; i <= m; i++){
        if(!cmpang(q[tail].v(),L[i].v())) continue;
        for(; head<tail && ToLeft(L[i].v(),Cross(q[tail-1],q[tail])-L[i][0]); --tail);
        for(; head<tail && ToLeft(L[i].v(),Cross(q[head+1],q[head])-L[i][0]); ++head);
        q[++tail] = L[i];
    }
    for(; head<tail && ToLeft(q[head].v(),Cross(q[tail-1],q[tail])-q[head][0]); --tail);
    for(; head<tail && ToLeft(q[tail].v(),Cross(q[head+1],q[head])-q[tail][0]); ++head);
    q[tail+1] = q[head]; for(rint i = head; i <= tail; R.push(Cross(q[i],q[i+1])), i++);
}

KD树

KD树

#define f(x,c) t[x].c
#define lc(x) t[x].c[0]
#define rc(x) t[x].c[1]
#define c(x,y) t[x].c[y]
struct O{int x[2];}dat[MAXN+5];
struct Node{int l, d, r, u, c[2];}t[MAXN+5]; bool kd; int n, rt, mn, mx, ans;
#define dis(a,b) (abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1])) // Manhattan Distance
inline bool cmp(O a, O b){return a.x[kd]-b.x[kd] ? a.x[kd]<b.x[kd] : a.x[!kd]<b.x[!kd];}
inline void Push(int p){
    for(rint k = 0; k < 2; k++) if(c(p,k))
        f(p,l) = min(f(p,l),f(c(p,k),l)), f(p,d) = min(f(p,d),f(c(p,k),d)),
        f(p,r) = max(f(p,r),f(c(p,k),r)), f(p,u) = max(f(p,u),f(c(p,k),u));
}
inline int Build(int lef, int rig, int dep){
    if(lef > rig) return 0; int mid = lef+rig>>1;
    kd = dep&1, nth_element(dat+lef,dat+mid,dat+rig+1,cmp);
    lc(mid) = Build(lef,mid-1,dep+1), rc(mid) = Build(mid+1,rig,dep+1);
    f(mid,l) = f(mid,r) = dat[mid].x[0], f(mid,d) = f(mid,u) = dat[mid].x[1]; Push(mid); return mid;
}
inline int Maxdis(int p, O a){
    return max(abs(a.x[0]-f(p,l)),abs(a.x[0]-f(p,r)))+max(abs(a.x[1]-f(p,d)),abs(a.x[1]-f(p,u)));
}
inline int Mindis(int p, O a){
    return max(f(p,l)-a.x[0],0)+max(a.x[0]-f(p,r),0)+max(f(p,d)-a.x[1],0)+max(a.x[1]-f(p,u),0);
}
inline void QMax(int p, O a){
    if(!p)  return; mx = max(mx,dis(dat[p],a));
    int lv = Maxdis(lc(p),a), rv = Maxdis(rc(p),a);
    if(lv > rv) lv > mx ? QMax(lc(p),a),0 : 0, rv > mx ? QMax(rc(p),a),0 : 0;
    else        rv > mx ? QMax(rc(p),a),0 : 0, lv > mx ? QMax(lc(p),a),0 : 0;
}

2D树(曼哈顿距离)

KD树

struct O{int x[5];}dat[MAXN+5], o; struct Node{int c[2];}t[MAXN+5];
typedef pair<int,int> pii; priority_queue<pii> q; int K, rt, kd;
inline int dis2(O a, O b, rint ans=0){
    for(rint d = 0; d < K; ans += sqr(a.x[d]-b.x[d]), d++); return ans;
}
inline bool cmp(O a, O b){return a.x[kd]-b.x[kd] ? a.x[kd]<b.x[kd] : a.x[!kd]<b.x[!kd];}
inline int Build(int lef, int rig, int dep){
    if(lef > rig) return 0; int mid = lef+rig>>1;
    kd = dep%K, nth_element(dat+lef,dat+mid,dat+rig+1,cmp);
    lc(mid) = Build(lef,mid-1,dep+1), rc(mid) = Build(mid+1,rig,dep+1); return mid;
}
inline void Query(int p, O &a, int dep){
    if(!p) return; kd = dep%K; int v = dis2(dat[p],a), r = cmp(dat[p],a); Query(c(p,r),a,dep+1);
    if(q.size()<M) q.push(pii(v,p)); else if(v<q.top().first) q.pop(), q.push(pii(v,p));
    kd = dep%K; if(q.size()<M||sqr(dat[p].x[kd]-a.x[kd])<q.top().first) Query(c(p,!r),a,dep+1);
}

KD树(欧几里得距离)

没有什么卵用但是加上总比不加要好的KD树各种剪枝优化.jpg

进阶(2D)解析几何

圆的(外)公切线

圆反演

反演是可逆双射

T = T^{-1}
T(P) = P' \text{ where } O \in PP', \vert OP \vert \vert OP' \vert = r^2

不过反演中心的直线

\Leftrightarrow

过反演中心的圆

不过反演中心的圆

\Leftrightarrow

不过反演中心的圆

(且半径之比等于到反演圆心距离之比)

反演不改变相切性

(自适应)辛普森积分

inline db Integ(db l, db r){
    static db m; m = (l+r)/2;
    return (r-l)/6*(F(l)+4*F(m)+F(r));
}
inline db Simpson(db l, db r, db S){
    db m = (l+r)/2, a = Integ(l,m), b = Integ(m,r);
    return fabs(a+b-S)<=EPS ? S+(a+b-S)/15 : Simpson(l,m,a)+Simpson(m,r,b);
}
\int_l^r f(x)\;\text{d}x \approx \frac{r-l}{6}\left(f(l)+4f(\frac{l+r}{2})+f(r)\right)
\frac{1}{15} ???

(自适应)辛普森积分

(第一次手动随机划分子区间/区间端点做微小扰动)

(3D)计算几何

混合积

a \cdot (b \times c) = \det \begin{bmatrix} a_1 & a_2 & a_3 \\ b_1 & b_2 & b_3 \\ c_1 & c_2 & c_3 \\ \end{bmatrix}

空间体体积

a,b,c三个向量构成的平行六面体有向体积为

a \cdot (b \times c)

若a,b,c构成右手系则有向体积为正, 左手系则有向体积为负

空间向量方向

空间平面法向量

b,c两个向量确定的平面法向量为

(\vec i, \vec j, \vec k) \cdot (b \times c)

空间三角形面积

\frac{1}{2} \vert (\vec i, \vec j, \vec k) \cdot (b \times c) \vert

或海伦公式

Fun Problem Time!

题目顺序是随机的

POJ 2242

求三角形外接圆周长

POJ 2242

正弦定理: 

d_{\text{circumcircle}} = \frac{a}{\sin A} = \frac{a}{\frac{\vert \vec b \times \vec c \vert}{bc}} = \frac{abc}{\vert \vec b \times \vec c \vert}

BZOJ 1502

BZOJ 1502

投影后圆心的位置:

x_i = \frac{\sum_{j=1}^i h_j}{\tan \alpha}

BZOJ 1502

投影后圆心的位置:

x_i = \frac{\sum_{j=1}^i h_j}{\tan \alpha}

投影后圆半径不变

BZOJ 1502

投影后圆心的位置:

x_i = \frac{\sum_{j=1}^i h_j}{\tan \alpha}

投影后圆半径不变

求出公切线后整个函数图像就确定了,要求函数面积

BZOJ 1502

投影后圆心的位置:

x_i = \frac{\sum_{j=1}^i h_j}{\tan \alpha}

投影后圆半径不变

求出公切线后整个函数图像就确定了,要求函数面积

\int_l^r f(x)\;\text{d}x \approx \frac{r-l}{6}\left(f(l)+4f(\frac{l+r}{2})+f(r)\right)

BZOJ 5317

\begin{aligned} & \text{给定两个实心凸多边形}A\text{和}B\text{,每次给出向量}v\text{,} \\ & \text{记实心多边形}C\text{为} \lbrace b+v \vert b \in B \rbrace \text{,} \\ & \text{求}A\text{和}C\text{是否有公共点。} \vert A \vert, \vert B \vert,q \le 10^5. \end{aligned}

BZOJ 5317

题目等价于:

\exists a \in A, b \in B, b + v = a \\ \Leftrightarrow v \in A-B \\
A-B?

BZOJ 5317

题目等价于:

\exists a \in A, b \in B, b + v = a \\ \Leftrightarrow v \in A-B \\
A-B?
A-B = A + (-B)
A+(-B)?

BZOJ 5317

题目等价于:

\exists a \in A, b \in B, b + v = a \\ \Leftrightarrow v \in A-B \\
A-B?
A-B = A + (-B)
A+(-B)?

Minkowski和

BZOJ 5317

题目等价于:

\exists a \in A, b \in B, b + v = a \\ \Leftrightarrow v \in A-B \\
A-B?
A-B = A + (-B)
A+(-B)?

Minkowski和

判断一个点位置?

BZOJ 5317

题目等价于:

\exists a \in A, b \in B, b + v = a \\ \Leftrightarrow v \in A-B \\
A-B?
A-B = A + (-B)
A+(-B)?

Minkowski和

判断一个点位置?

极角排序+二分

UOJ 326

\begin{aligned} & \text{给定平面上}n\text{个红点和}m\text{个蓝点,} \\ & \text{对于每对红点}P_iP_j\text{,求:} \\ & \Delta OP_iP_j\text{内是否有至少一个蓝点,} \\ & \text{输出任意一个蓝点或}-1\text{。} \\ & n,m \le 4000 \end{aligned}

显然只有在极角\(OP_i\)到\(OP_j\)范围内的点是有用的

UOJ 326

显然只有在极角\(OP_i\)到\(OP_j\)范围内的点是有用的

UOJ 326

进一步,只需要记录极角序最小的即可

\begin{aligned} & \text{给定球面上顺序}n\text{个点,相邻两点之间走球面最短路,} \\ & \text{判断是否任何大圆都经过这条回路(接触也算作经过)。} \\ & n \le 5000, T \le 200. \\ \end{aligned}

等价于判断是否整个回路上所有点都严格在大圆的同一侧。

等价于判断是否整个回路上所有点都严格在大圆的同一侧。

对于一个确定的大圆,枚举每个点,三维混合积判断即可。

枚举大圆?

等价于判断是否整个回路上所有点都严格在大圆的同一侧。

对于一个确定的大圆,枚举每个点,三维混合积判断即可。

枚举大圆?

\sqrt{}

枚举两个点,其与圆心确定的平面作为大圆的可能选择

O(Tn^3)

等价于判断是否整个回路上所有点都严格在大圆的同一侧。

对于一个确定的大圆,枚举每个点,三维混合积判断即可。

枚举大圆?

\sqrt{}

枚举两个点,其与圆心确定的平面作为大圆的可能选择

O(Tn^3)
random_shuffle(p+1,p+n+1)

等价于判断是否整个回路上所有点都严格在大圆的同一侧。

对于一个确定的大圆,枚举每个点,三维混合积判断即可。

枚举大圆?

\sqrt{}

枚举两个点,其与圆心确定的平面作为大圆的可能选择

O(Tn^3)
random_shuffle(p+1,p+n+1)

接触也合法,可以把大圆沿法向量翻转一个小角度

TopCoder 10308

\begin{aligned} & \text{给定两个凸包}C_1, C_2\text{,}C_2\text{严格包含在}C_1\text{内,} \\ & \text{如果从}C_1\text{的边界上等概率选择一个点}x\text{,} \\ & \text{求从}x\text{到「}C_1\text{边界上距离}x\text{最远的点」的连线与}C_2\text{有交的概率。} \\ & \vert C_1 \vert, \vert C_2 \vert \le 50. \\ \end{aligned}

考虑贡献法

TopCoder 10308

p_i\text{什么时候会成为}\text{「}C_1\text{边界上距离}x\text{最远的点」?}

考虑贡献法

TopCoder 10308

p_i\text{什么时候会成为}\text{「}C_1\text{边界上距离}x\text{最远的点」?}
\forall p_j, \text{dis}(x,p_i) \ge \text{dis}(x,p_j)

考虑贡献法

TopCoder 10308

p_i\text{什么时候会成为}\text{「}C_1\text{边界上距离}x\text{最远的点」?}

枚举点和    做中垂线,所有中垂线靠近    一侧的半平面交就是所有最远点是    的点的集合。

p_i
p_i
p_i
\forall p_j, \text{dis}(x,p_i) \ge \text{dis}(x,p_j)

考虑贡献法

TopCoder 10308

p_i\text{什么时候会成为}\text{「}C_1\text{边界上距离}x\text{最远的点」?}

枚举点和    做中垂线,所有中垂线靠近    一侧的半平面交就是所有最远点是    的点的集合。

p_i
p_i
p_i

然后算出经过     的角度,再和     边界取交即可

C_2
C_1
\forall p_j, \text{dis}(x,p_i) \ge \text{dis}(x,p_j)

TopCoder 10308

ZROJ 76

\begin{aligned} & \text{有限矩形平面内给定}n{个点,} \\ & \text{求一个任意的、距离这}n{个点中} \\ & \text{「不严格第二近邻」最远的点。} \\ & n \le 1500. \\ \end{aligned}

二分答案(第二近邻距离),那么答案点必然在圆弧上

ZROJ 76

二分答案(第二近邻距离),那么答案点必然在圆弧上

ZROJ 76

这个点是第二近邻,当且仅当其在另一个圆内(或圆上)

二分答案(第二近邻距离),那么答案点必然在圆弧上

ZROJ 76

这个点是第二近邻,当且仅当其在另一个圆内(或圆上)

也就是判断是否存在一段圆弧是否被其他圆覆盖恰好一次

二分答案(第二近邻距离),那么答案点必然在圆弧上

ZROJ 76

这个点是第二近邻,当且仅当其在另一个圆内(或圆上)

也就是判断是否存在一段圆弧是否被其他圆覆盖恰好一次

圆求交、圆弧求交(由于等半径,所以圆求交很好做)

二分答案(第二近邻距离),那么答案点必然在圆弧上

ZROJ 76

这个点是第二近邻,当且仅当其在另一个圆内(或圆上)

也就是判断是否存在一段圆弧是否被其他圆覆盖恰好一次

圆求交、圆弧求交(由于等半径,所以圆求交很好做)

事实上小于等于一次即可,如果一个点是最近邻,第二近邻一定更远

注意圆还要和矩形边界求交

BZOJ 1069

\begin{aligned} & \text{给定平面}n\text{个点,求选择其中的}4\text{个点,} \\ & \text{最大化所形成的四边形面积。} n \le 2000. \\ \end{aligned}

显然这四个点都在凸包上

BZOJ 1069

显然这四个点都在凸包上

BZOJ 1069

枚举对角线上两个点,两侧都要求面积最大的三角形

显然这四个点都在凸包上

BZOJ 1069

枚举对角线上两个点,两侧都要求面积最大的三角形

枚举左端点,一边枚举右端点一边旋转卡壳

O(n^2)

BZOJ 1069

db RC(Polygon &R, db Ans=0){
    for(rint l = (R[R.n+1] = R[1], 1), r, i, j; l <= R.n; l++)
        for(i = l%R.n+1, r = l+2, j = r%R.n+1; r <= R.n; r++){
            for(; i%R.n+1!=r && (R[i]-R[l])%(R[r]-R[l]) < (R[i+1]-R[l])%(R[r]-R[l]); i = i%R.n+1);
            for(; j%R.n+1!=l && (R[j]-R[r])%(R[l]-R[r]) < (R[j+1]-R[r])%(R[l]-R[r]); j = j%R.n+1);
            Ans = max(Ans,(R[i]-R[l])%(R[r]-R[l])+(R[j]-R[r])%(R[l]-R[r]));
        }   return Ans/2.;
}

HDU 4773

\begin{aligned} & \text{给定两个相离的圆和一个不在圆上的点}O\text{,} \\ & \text{求所有经过该点且与两个圆都外切的圆。} \\ \end{aligned}

当然只能是圆反演了

HDU 4773

当然只能是圆反演了

HDU 4773

对点O做反演,原来的两个圆都会边长位似圆,现在要求的答案也就是外公切线了。

当然只能是圆反演了

HDU 4773

对点O做反演,原来的两个圆都会边长位似圆,现在要求的答案也就是外公切线了。

怎么判断外公切线和内公切线

当然只能是圆反演了

HDU 4773

对点O做反演,原来的两个圆都会边长位似圆,现在要求的答案也就是外公切线了。

怎么判断外公切线和内公切线

其实本来就是只有外公切线

Codeforces 975E

\begin{aligned} & \text{给定一个凸多边形,一开始多边形的点}1\text{和}2\text{固定,} \\ & \text{每次取消某个固定点(多边形由于重力旋转到势能最低状态),} \\ & \text{然后再将这个点固定在某个点}j\text{。} \\ & q\text{次查询某个顶点的坐标。} \\ & n \le 10^4, q \le 2 \times 10^5. \\ \end{aligned}

只需要维护重心以及重心到每个点的向量即可。每次重力作用相当于是将某个重心到点的向量旋转为竖直向上。

Codeforces 975E

向量旋转

计算角度

多边形重心

只需要维护重心以及重心到每个点的向量即可。每次重力作用相当于是将某个重心到点的向量旋转为竖直向上。

Codeforces 975E

向量旋转

计算角度

多边形重心

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

BZOJ 2732

\begin{aligned} & \text{给定平面上}n\text{条平行于}y\text{轴的线段,} \\ & \text{求如果做一条原点开始的抛物线}y = ax^2+bx(a \lt 0, b \gt 0)\text{,} \\ & \text{最多可以穿过前几条线段(恰好过端点也算作穿过)。} n \le 10^5. \\ \end{aligned}

BZOJ 2732

考虑线段(x,[l,r]):

\begin{aligned} & l \le x^2a + xb \le r \\ \Leftrightarrow & b \le - x \cdot a + \frac{r}{x} \text{ and } b \ge -x \cdot a + \frac{l}{x} \end{aligned}

BZOJ 2732

考虑线段(x,[l,r]):

\begin{aligned} & l \le x^2a + xb \le r \\ \Leftrightarrow & b \le - x \cdot a + \frac{r}{x} \text{ and } b \ge -x \cdot a + \frac{l}{x} \end{aligned}

(a,b)点集的半平面交

ZROJ 144

\begin{aligned} & \text{给定}3\text{个凸多边形,多组询问:} \\ & \text{是否可以在每个多边形内部(不严格)选择一个点,} \\ & \text{使得这三个点的重心恰好落在}(x,y)\text{。} \\ & n,m \le 10^5. \\ \end{aligned}

ZROJ 144

三角形重心

(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3})

ZROJ 144

三角形重心

(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3})
\exists (x,y) \in \frac{A}{3} + \frac{B}{3} + \frac{C}{3}

ZROJ 144

三角形重心

(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3})
\exists (x,y) \in \frac{A}{3} + \frac{B}{3} + \frac{C}{3}

Minkowski和

ZROJ 144

三角形重心

(\frac{x_1+x_2+x_3}{3},\frac{y_1+y_2+y_3}{3})
\exists (x,y) \in \frac{A}{3} + \frac{B}{3} + \frac{C}{3}

Minkowski和

判断一个点位置?

极角排序+二分

(似曾相识)

BZOJ 1100

\begin{aligned} & \text{顺序给定一个不自交多边形的顶点,求对称轴数。} \\ & n \le 10^5. \\ \end{aligned}

Mix

BZOJ 1100

Mix

将一个多边形哈希成一个字符串(例如「叉积+边长序列)

BZOJ 1100

Mix

将一个多边形哈希成一个字符串(例如「叉积+边长序列)

轴对称

倍长串的最长回文子串长度

\Leftrightarrow
\ge n

SGU 198

\begin{aligned} & \text{给定平面上n个位置关系任意的圆,以及一个不和} \\ & \text{其他任何圆相交的圆。求这个圆能否保持和其他} \\ & \text{圆不相交的情况下,移动到无穷远处。} \\ & n \le 300. \\ \end{aligned}

Mix

SGU 198

Mix

可以将这个圆的半径加到其他圆上,这个圆变为一个点。

SGU 198

Mix

可以将这个圆的半径加到其他圆上,这个圆变为一个点。

相交的圆之间连一条边,问题就是是否存在一个闭合区域(多边形)包含了当前点。

SGU 198

Mix

可以将这个圆的半径加到其他圆上,这个圆变为一个点。

相交的圆之间连一条边,问题就是是否存在一个闭合区域(多边形)包含了当前点。

如果点在多边形内和为2π或-2π,否则和为0。那么问题就相当于求是否所有环的有向夹角和都为0。

SGU 198

Mix

可以将这个圆的半径加到其他圆上,这个圆变为一个点。

相交的圆之间连一条边,问题就是是否存在一个闭合区域(多边形)包含了当前点。

如果点在多边形内和为2π或-2π,否则和为0。那么问题就相当于求是否所有环的有向夹角和都为0。

注意到对于一对反向的边,其有向夹角相反,存在和为X的环就一定存在和为-X的环。问题就转化为求是否有负环。

SGU 198

Mix

可以将这个圆的半径加到其他圆上,这个圆变为一个点。

相交的圆之间连一条边,问题就是是否存在一个闭合区域(多边形)包含了当前点。

如果点在多边形内和为2π或-2π,否则和为0。那么问题就相当于求是否所有环的有向夹角和都为0。

注意到对于一对反向的边,其有向夹角相反,存在和为X的环就一定存在和为-X的环。问题就转化为求是否有负环。

SPFA判负环

Codeforces 704E

\begin{aligned} & \text{一棵树上}m\text{个事件:} \\ & \text{「一个点从}t_i\text{时刻开始以每秒}c_i\text{条边的速度从}u_i\text{移动向}v_i\text{」} \\ & \text{求最早相遇的两个点的相遇时间(可能为小数)。} \\ & n,m \le 10^5, t_i,c_i \le 10^4\text{,精度误差} \le 10^{-6}. \\ \end{aligned}

Mix

Codeforces 704E

Mix

考虑链上问题,将时间看成x轴,下标看成y轴,所求的是最左侧的线段交点。

Codeforces 704E

Mix

考虑链上问题,将时间看成x轴,下标看成y轴,所求的是最左侧的线段交点。

这有一个神奇的特点: 在发现这个交点之前,线段是无交的。换言之,是存在良序定义的。

Codeforces 704E

Mix

考虑链上问题,将时间看成x轴,下标看成y轴,所求的是最左侧的线段交点。

这有一个神奇的特点: 在发现这个交点之前,线段是无交的。换言之,是存在良序定义的。

用              维护。

std::set

Codeforces 704E

Mix

考虑链上问题,将时间看成x轴,下标看成y轴,所求的是最左侧的线段交点。

这有一个神奇的特点: 在发现这个交点之前,线段是无交的。换言之,是存在良序定义的。

用              维护。

std::set

树上问题?

Codeforces 704E

Mix

考虑链上问题,将时间看成x轴,下标看成y轴,所求的是最左侧的线段交点。

这有一个神奇的特点: 在发现这个交点之前,线段是无交的。换言之,是存在良序定义的。

用              维护。

std::set

树上问题?

树链剖分,把所有线段分解到DFS序区间上

BZOJ 2391

\begin{aligned} & \text{给定平面上}m\text{个有权值的点和一个多边形} \\ & \text{多次查询一个「子顶点形成的多边形」内点权和。} \\ & n,m \le 1000, q \le 10000. \\ \end{aligned}

Mix

三角剖分

BZOJ 2391

Mix

三角剖分

BZOJ 2391

每个小三角形怎么统计点数?

Mix

三角剖分

BZOJ 2391

每个小三角形怎么统计点数?

类似于Range Tree的思想,不过是暴力Range Tree

Mix

UOJ 326 ++

三角剖分

BZOJ 2391

每个小三角形怎么统计点数?

类似于Range Tree的思想,不过是暴力Range Tree

n棵平衡树

Mix

UOJ 326 ++

BZOJ 5316

\begin{aligned} & \text{给定平面上}n\text{个不区分的点和一个放大了}R\text{倍的单位圆,} \\ & \text{每个点独立行动,求所有点在圆上等距分布所需最小时间。} \\ & n \le 200, \vert x_i \vert, \vert y_i \vert, \vert R \vert \le 100. \\ \end{aligned}

Mix

BZOJ 5316

Mix

二分答案,然后求出每个点能到达的圆的圆弧(的辐角区间),然后枚举角度看是否存在二分图完备匹配即可。

枚举角度?

BZOJ 5316

Mix

二分答案,然后求出每个点能到达的圆的圆弧(的辐角区间),然后枚举角度看是否存在二分图完备匹配即可。

枚举角度?

一定存在一种方案使得某个点卡在端点上。因此只有      个旋转角。

2n

BZOJ 5316

Mix

二分答案,然后求出每个点能到达的圆的圆弧(的辐角区间),然后枚举角度看是否存在二分图完备匹配即可。

枚举角度?

一定存在一种方案使得某个点卡在端点上。因此只有      个旋转角。

2n

二分图匹配Dinic复杂度                     ,总复杂度约为

O(m \sqrt n)
O(n^{3.5} \log R)

BZOJ 5316

Mix

二分答案,然后求出每个点能到达的圆的圆弧(的辐角区间),然后枚举角度看是否存在二分图完备匹配即可。

网络流退流

一定存在一种方案使得某个点卡在端点上。因此只有      个旋转角。

2n

二分图匹配Dinic复杂度                     ,总复杂度约为

O(m \sqrt n)
O(n^{3.5} \log R)

枚举角度?

O(n^{3} \log R)

BZOJ 5328

Mix

Mix

旋转一下

BZOJ 5328

Mix

旋转一下

BZOJ 5328

扫描线

Mix

旋转一下

BZOJ 5328

然后李超树随便一个什么数据结构维护一下就可以了

扫描线

Mix

旋转一下

BZOJ 5328

然后李超树随便一个什么数据结构维护一下就可以了

扫描线

(推荐手写尝试)

SGU 303

\begin{aligned} & \text{输入}n\text{条只在端点处相交的线段,线段有权值,构成闭合图形,} \\ & \text{给定两点}S,T\text{,保证}S,T\text{不在线段上或无限大区域内,} \\ & \text{求选择原图线段中的一个子集构成一个简单多边形,使得:} \\ & S\text{不可能不经过多边形边到达}T\text{,输出最小代价方案。} \\ & \text{保证有解,}n \le 300, \text{所有点坐标绝对值} \le 10^4. \\ \end{aligned}

Mix

SGU 303

Mix

实际上就是在求平面图最小割

SGU 303

Mix

实际上就是在求平面图最小割

= 对偶图最短路

SGU 303

Mix

实际上就是在求平面图最小割

= 对偶图最短路

最小左转法建对偶图

THUWC 2019 D2T3

\begin{aligned} & \text{给定平面上}n\text{个点,从所有} \\ & \text{「以其中若干个点为顶点的凸多边形」} \\ & \text{中选出一个凸多边形,求选出的凸多边形的面积的期望和方差。} \\ & n \le 500 \\ \end{aligned}

Mix

Mix

THUWC 2019 D2T3

凸多边形面积当然是要拆开每条边算了(经典操作)

Mix

THUWC 2019 D2T3

凸多边形面积当然是要拆开每条边算了(经典操作)

方差当然也是要拆开了(经典操作)

\begin{aligned} \sigma &= \frac{1}{n}\sum (x_i-\overline x)^2 \\ &= \frac{1}{n}\left (\sum x_i^2 \right) - \frac{2\overline x}{n}\left(\sum x_i\right) + \frac{1}{n} \left( \sum \overline x^2\right) \\ &= \frac{1}{n}\left (\sum x_i^2 \right) - \overline x^2 \\ &= \overline{x^2} - \overline x^2 \\ \end{aligned}

(即:方差 = 平方的期望 - 期望的平方)

Mix

THUWC 2019 D2T3

f[a][c][d] = \sum_b f[a][b][c] \\ g[a][c][d] = \sum_b g[a][b][c]+f[a][b][c] \cdot s_{c,d} \\ h[a][c][d] = \sum_b h[a][b][c] + 2 \cdot g[a][b][c] \cdot s_{c,d} + f[a][b][c] \cdot s_{c,d}^2 \\

于是只需要维护方案数(0次方期望),面积(1次方期望),面积平方和(2次方期望)即可。

Mix

THUWC 2019 D2T3

f[a][c][d] = \sum_b f[a][b][c] \\ g[a][c][d] = \sum_b g[a][b][c]+f[a][b][c] \cdot s_{c,d} \\ h[a][c][d] = \sum_b h[a][b][c] + 2 \cdot g[a][b][c] \cdot s_{c,d} + f[a][b][c] \cdot s_{c,d}^2 \\

于是只需要维护方案数(0次方期望),面积(1次方期望),面积平方和(2次方期望)即可。

O(n^4)

Mix

THUWC 2019 D2T3

f[a][c][d] = \sum_b f[a][b][c] \\ g[a][c][d] = \sum_b g[a][b][c]+f[a][b][c] \cdot s_{c,d} \\ h[a][c][d] = \sum_b h[a][b][c] + 2 \cdot g[a][b][c] \cdot s_{c,d} + f[a][b][c] \cdot s_{c,d}^2 \\

于是只需要维护方案数(0次方期望),面积(1次方期望),面积平方和(2次方期望)即可。

O(n^4)

注意到(b,c)和(c,d)需要满足极角序单调关系,可以前缀和优化。

O(n^3)
\begin{aligned} & \text{给定平面上}n\text{个点和一个多边形} \\ & \text{将多边形随机旋转一个角度,求:} \\ & \text{多边形旋转后覆盖的点数的期望。} \\ & n \le 200, m \le 500, \vert x_i \vert, \vert y_i \vert \le 10^6. \\ \end{aligned}

Mix

Mix

三角剖分

Mix

三角剖分

考虑将旋转多边形,改为旋转点集

Mix

三角剖分

考虑将旋转多边形,改为旋转点集

就是圆和三角形求交

Mix

三角剖分

考虑将旋转多边形,改为旋转点集

就是圆和三角形求交

圆线求交与圆弧交

THUSC 2016 T3 星露谷物语

Mix

Mix

n \le 10

Mix

点到直线距离公式·高维版

d = \frac{c_0+c_1x_1+c_2x_2+ \cdots +c_nx_n}{\sqrt{c_1^2+c_2^2+ \cdots +c_n^2}} = \frac{c_0 + c \cdot x}{\| c \|_2}

Mix

点到直线距离公式·高维版

\frac{c_0 + c \cdot x_i}{\| c \|_2} = r_i
d = \frac{c_0+c_1x_1+c_2x_2+ \cdots +c_nx_n}{\sqrt{c_1^2+c_2^2+ \cdots +c_n^2}} = \frac{c_0 + c \cdot x}{\| c \|_2}

高斯消元

Mix

点到直线距离公式·高维版

\frac{c_0 + c \cdot x_i}{\| c \|_2} = r_i
d = \frac{c_0+c_1x_1+c_2x_2+ \cdots +c_nx_n}{\sqrt{c_1^2+c_2^2+ \cdots +c_n^2}} = \frac{c_0 + c \cdot x}{\| c \|_2}

高斯消元

n个方程,n+1个变量?

Mix

点到直线距离公式·高维版

\frac{c_0 + c \cdot x_i}{\| c \|_2} = r_i
d = \frac{c_0+c_1x_1+c_2x_2+ \cdots +c_nx_n}{\sqrt{c_1^2+c_2^2+ \cdots +c_n^2}} = \frac{c_0 + c \cdot x}{\| c \|_2}

高斯消元

n个方程,n+1个变量?

其实无所谓,设成是个定值

\| c \|_2

Thank You