110 選手班 - 計算幾何

向量運算

• 加法
• 減法
• 乘法
• 除法

using GT = long long ;
struct Pt {
    GT x, y ;
    
    Pt operator+(const Pt b) const {
        return Pt{x+b.x, y+b.y} ;
    }
    Pt operator-(const Pt b) const {
        return Pt{x-b.x, y-b.y} ;
    }
    Pt operator*(const GT b) const {
        return Pt{x*b, y*b} ;
    }
    Pt operator/(const GT b) const {
        return Pt{x/b, y/b} ;
    }
    bool operator==(const Pt b) const {
        return x == b.x && y == b.y ;
    }
    double len () {
        return sqrt(x*x + y*y) ;
    }
    GT norm () {
        return x*x + y*y ;
    }
};

Dot

• 內積
• \((x_1, y_1) \cdot (x_2, y_2)=x_1x_2 + y_1y_2\)
• 兩個向量在同一方向的程度

Cross

• 外積
• \((x_1, y_1) \times (x_2, y_2)=x_1y_2 - x_2y_1\)
• 兩個向量的垂直程度，逆時鐘為正

GT dot(Pt a, Pt b) {
    return a.x * b.x + a.y * b.y ;
}
GT cross(Pt a, Pt b) {
    return a.x * b.y - a.y * b.x ;
}

Orientation

• 兩個向量的方向性
  • 逆時針：1
  • 順時針：-1
  • 平行：0
• cross

int ori(Pt a, Pt b) {
    GT ret = cross(a, b) ;
    if(ret == 0) return 0 ;
    return ret < 0 ? -1 : 1 ;
}

Area

• 兩個夾角形成有向面積
  • 逆時針：正數
  • 順時針：負數
• \(\vec{A} 與 \vec{B}\) 的夾角面積：\(\vec{A} \times \vec{B}\)

多邊形面積

• 切成到原點的多個三角形
• 依照點的順序計算有向面積加總

In Segment

• 給定一個點及線段
• 請判斷點是否在線段內

• 線段 \((A,B)\)，點 \(P\)
• 直線上：\(\text{cross}(\overrightarrow{AB}, \overrightarrow{AP}) = 0\)
• 線段內：\(\text{dot}(\overrightarrow{PA}, \overrightarrow{PB}) \leq 0\)

bool in_segment(Pt a, Pt b, Pt p){
    return ori(b-a, p-a) == 0 && dot(p-a, p-b) <= 0 ;
}

Segment Intersection

• 給定兩個線段
• 請判斷兩個線段是否相交

• 線段 \((A,B)\)，\((C,D)\)
• 只有一個點在線段內：in_segment
• 嚴格相交：將彼此切割成兩半
  • \(\text{ori}(\overrightarrow{AB}, \overrightarrow{AC}) \times \text{ori}(\overrightarrow{AB}, \overrightarrow{AD}) < 0\)
  • \(\text{ori}(\overrightarrow{CD}, \overrightarrow{CA}) \times \text{ori}(\overrightarrow{CD}, \overrightarrow{CB}) < 0\)

bool banana(Pt a, Pt b, Pt c, Pt d) {
    if( in_segment(a, b, c) || in_segment(a, b, d) ||
        in_segment(c, d, a) || in_segment(c, d, b))
        return true ;
    return ori(b-a, c-a) * ori(b-a, d-a) < 0 &&
           ori(d-c, a-c) * ori(d-c, b-c) < 0 ; 
}

Trigonometric Functions

• \(\cos(\theta)\) \ \(\sin(\theta)\) \ \(\tan(\theta)\)
• \(\theta\) 參數為弧度制
• Time > \(\mathcal{O}(1)\)
• 用泰勒展開式等實作

atan2

• Returns the principal value of the arc tangent of y/x, expressed in radians. –cplusplus.com
• 回傳值域：\((-\pi, \pi]\)
  

Solution 1

• sort by atan2

bool cmp(Pt a, Pt b) {
    return atan2(a.x, a,y) < atan2(b.x, b.y) ;
}

• 優點：直觀、簡單
• 缺點：慢、浮點數誤差

Solution 2

• sort by cross

bool cmp(Pt a, Pt b) {
    bool f1 = a.x < 0 || (a.x == 0 && a.y < 0) ;
    bool f2 = b.x < 0 || (b.x == 0 && b.y < 0) ;
    if(f1 != f2) return f1 < f2 ;
    return cross(a, b) > 0 ;
}

• 切成兩半，各自外積判斷
• 優點：快速、正確
• 缺點：麻煩

Convex

• 凸多邊形
• 圖形內任兩點連線皆在圖形內部
• 所有內角小於 \(180\) 度

Convex Hull

• 包含所有點的最小凸多邊形
  

Andrew's Monotone Chain

• 將所有點依照 \((x,y)\) 排序
• 把下凸包圍出來
• 把上凸包圍出來
• 合併上下凸包

圍下凸包

• 兩條邊的內角小於 \(180\) 度
• 點 \(A, B, C\) 依照 \((x,y)\) 排序
• 若 \(\text{cross}(\overrightarrow{AB}, \overrightarrow{BC}) \leq 0\) 則 \(B\) 不在凸包上

• 以 stack 維護目前凸包
• 對於新加入的點，檢查前一個點是否在凸包上
• 下凸包：\(0 \rightarrow N\) 逆時針旋轉
• 上凸包：\(N \rightarrow 0\) 逆時針旋轉

https://upload.wikimedia.org/wikipedia/commons/9/9a/Animation_depicting_the_Monotone_algorithm.gif

Time Complexity

• Sort：\(\mathcal{O}(N\log N)\)
• Construct：\(\mathcal{O}(N)\)
• Total：\(\mathcal{O}(N\log N)\)

vector<Pt> convex(vector<Pt> v){
    vector<Pt> ret ;
    sort(v.begin(), v.end()) ;
    int k = 0 ;
    
    for(auto i:v){
        while(k >= 2 && ori(ret[k-1] - ret[k-2], i - ret[k-1]) <= 0)
            ret.pop_back();
        ret.push_back(i) ;
        ++k ;
    }
    v.pop_back();
    int hf = --k ;
    
    reverse(v.begin(), v.end());
    for(auto i:v){
        while(k - hf >= 2 && ori(ret[k-1] - ret[k-2], i - ret[k-1]) <= 0)
            ret.pop_back();
        ret.push_back(i) ;
        ++k ;
    }
    
    return ret;
}

Application

• 最大值問題
  • 最遠點對
  • 最小包覆矩形
• 旋轉卡尺
  • 邊斜率單調
  • 最大三角形

http://www-cgrl.cs.mcgill.ca/~godfried/research/calipers.html

整數點限制

• 座標範圍 \([0,C]\)
• 凸包上至多 \(\mathcal{O}(\sqrt C)\) 個點
• 直接暴力枚舉最遠點對

直線與凸包

• 把一堆直線丟進平面
• 若只關心最上方的函數，將會形成一個下凸包

Envelope

• 快速尋找某個 \(x\) 在多個線性函數下的最大值
• Find \(\max(f_i(x)=a_ix+b_i)\)
• 凸包上的函數斜率具有單調性
• 對函數三分搜 \(\mathcal{O}(\log N)\)
• DP 斜率優化

Problem

• 給定 \(N\) 個點
• 請支援以下詢問 \(Q\) 次
  • 給定一條直線 \(f(x) = ax + b\)，請問是否所有點皆在直線上方？
• \(N, Q \leq 10^6\)

• \(\forall i,\ y_i \geq f(x_i) = ax_i + b\)
• \(-b \geq ax_i - y_i\)
• \((-b) \geq x_i (a) - y_i\)
• 點 \((a, -b)\) 在直線 \(f(t) = x_i(t) - y_i\) 上方

• 所有點 \((x_i, y_i)\) 在直線 \(f(x) = ax+b\) 上方
• \(\Rightarrow\) 點 \((a, -b)\) 在所有直線 \(f_i(t) = x_i(t) - y_i\) 上方
• \(\Rightarrow\) 點 \((a, -b)\) 在所有直線 \(f_i(t)\) 所構造出的下凸包之上

• 排序所有直線 \(f_i(t)\)：\(\mathcal{O}(N\log N)\)
• 每次詢問檢查點是否在凸包上方：\(\mathcal{O}(\log N)\)
• Total：\(\mathcal{O}(N\log N + Q\log N)\)

Key

• 對偶性質：點 \(\Longleftrightarrow\) 直線
• 多個點與一條線 \(\Longleftrightarrow\) 多條線與一個點
• 改變題目的性值以幫助解題

類題

• CF 678F