Codeforces Gym 100517 K：凸包上線段相交對數計算（二分+向量）

問題描述

給定頂點按順時針順序的凸包 (n ≤ 100,000)，以及嚴格在內部的兩點 A, B。求凸包上有多少對頂點 (p_i, p_j) 使得線段 p_i p_j 與線段 AB 嚴格相交（交點不在端點）。

幾何觀察與二分

• 凸包上任意兩點連線將凸包分為兩部分。AB 在內部，故存在唯一的一對切線方向將凸包分為「AB 左側」與「右側」頂點集合。
• 對固定 i，p_i p_j 與 AB 相交 ⇔ p_j 落在 p_i 相對於 AB 的「對側」區間。利用叉積判斷點在有向線左側/右側。
• 將頂點數組複製一倍 (2n) 以處理循環。枚舉 i=1..n，在 [i+1, i+n-1] 中二分找到最靠近 AB 兩側的邊界點。

同方向判斷 (叉積)

向量 v1 = A - p_i, v2 = B - p_i。對候選點 p_mid，向量 v = p_mid - p_i。若 cross(v, v1) 與 cross(v, v2) 同號（或一個為 0），則 p_mid 在同側。

演算法流程

1. 讀入凸包頂點 p[1..n]，A, B。
2. p[n+1..2n] = p[1..n]。
3. 對每個 i=1..n：
   • 二分找第一個使 cross(v, v1) ≤ 0 且 cross(v, v2) ≤ 0 的位置 tp1（右側邊界）。
   • 二分找最後一個使 cross(v, v1) ≥ 0 且 cross(v, v2) ≥ 0 的位置 tp2（左側邊界）。
   • 若 tp1 ≠ tp2，合法 j 數為 tp1 - tp2 - 1，累加答案。
4. 最終答案除以 2（每對計算兩次）。

複雜度

• 時間：O(n log n)。
• 空間：O(n)。

參考程式碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pt { ll x, y; };
Pt operator-(Pt a, Pt b) { return {a.x-b.x, a.y-b.y}; }
ll cross(Pt a, Pt b) { return a.x*b.y - a.y*b.x; }
int sgn(ll x) { return (x>0)-(x<0); }

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n; Pt A, B;
    while (cin >> n) {
        vector p(2*n+1);
        for (int i=1;i<=n;i++) cin >> p[i].x >> p[i].y;
        cin >> A.x >> A.y >> B.x >> B.y;
        for (int i=n+1;i<=2*n;i++) p[i] = p[i-n];
        ll ans = 0;
        for (int i=1;i<=n;i++) {
            Pt v1 = A - p[i], v2 = B - p[i];
            int l = i+1, r = i+n-1;
            // 找右側邊界
            while (l < r) {
                int mid = (l+r)>>1;
                Pt v = p[mid] - p[i];
                if (sgn(cross(v, v1)) <= 0 && sgn(cross(v, v2)) <= 0) r = mid;
                else l = mid+1;
            }
            int tp1 = l;
            l = i+1; r = i+n-1;
            // 找左側邊界
            while (l < r) {
                int mid = (l+r+1)>>1;
                Pt v = p[mid] - p[i];
                if (sgn(cross(v, v1)) >= 0 && sgn(cross(v, v2)) >= 0) l = mid;
                else r = mid-1;
            }
            int tp2 = l;
            if (tp1 != tp2) ans += tp1 - tp2 - 1;
        }
        cout << (ans/2) << '\n';
    }
    return 0;
}