头像

我很可爱请给我钱

${qwq}$




离线:5小时前


最近来访(2438)
用户头像
封禁用户
用户头像
风不会停息_6
用户头像
只不过是镜花水月
用户头像
qaqsdf
用户头像
x834519823
用户头像
Forever_Czz
用户头像
疾风勇士
用户头像
zhhh
用户头像
AC86
用户头像
纯路人
用户头像
狂气电波
用户头像
做梦都在吃花卷
用户头像
梦忆晴天
用户头像
lweakmzs
用户头像
__ver
用户头像
fujang
用户头像
辣鸡号航母
用户头像
15163669008
用户头像
kurukuru
用户头像
WA_FOREVER


$\;\;\;\;$ 当双指针判定合法需要用到一些不具备区间可减性的信息时,例如区间$gcd$,当然可以用线段树$/st$表快速取出区间进行判断,但这样的话复杂度会多个$log$,那么有没有仍然线性的方法呢$qwq$,当然是有的,不然我也不会写这个。
$\;\;\;\;$ 先来看一道例题$Coprime\;Segment$,题目大意:找出一段最短的连续区间使得区间$gcd$为$1$。那么这题怎么做呢,我们维护两个栈,一个是插入栈,一个是删除栈,当插入元素的时候直接$push$入插入栈,注意这里插入的时候不仅仅是插入元素,还要计算我们需要的信息,也就是当前插入元素与栈中所有元素的$gcd$,而当删除的时候,我们从删除栈中$pop$栈顶,那如果删除栈是空的怎么办呢,这时就将插入栈中所有元素按照$pop$顺序插入删除栈,容易发现将元素按$pop$序插入另一个栈后,栈顶元素是最早插入的元素,之后再$pop$删除栈的栈顶也就是我们要删除的元素了,也就是说,以某一次“倒置”操作为分界点,左半边都在删除栈里,右半边都在插入栈里,而两个栈的栈顶就是我们需要的这段区间左半和右半的全部信息,这时只要取出栈顶进行信息合并就可以得到想要的信息了,每个元素只会最多入栈两次出栈两次,如果我们忽略$gcd$的复杂度,复杂度仍为线性。

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

using i64 = long long;

int n;
i64 a[N];

struct Stack {
    i64 stk[N];
    i64 gcd[N];
    int tt;
    void push(i64 x) {
        ++tt;
        stk[tt] = x;
        gcd[tt] = __gcd(stk[tt], gcd[tt - 1]);
    }
    i64 pop() {
        i64 ret = stk[tt];
        tt--;
        return ret;
    }
    bool empty() {
        return !tt;
    }
    i64 top() {
        return stk[tt];
    }
    i64 val() {
        return gcd[tt];
    }
};

struct AdjointStack {
    Stack s1, s2;
    void push(i64 x) {
        s2.push(x);
    }
    void pop() {
        if (s1.empty())
            while (!s2.empty()) 
                s1.push(s2.pop());
        s1.pop();
    }
    i64 val() {
        return __gcd(s1.val(), s2.val());
    }
}s;

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n;
    int res = 1e9;
    for (int i = 1, j = 1; i <= n; i++) {
        cin >> a[i];
        s.push(a[i]);
        while (j <= i && s.val() == 1) {  
            res = min(res, i - j + 1);
            s.pop(), j++;
        }
    }
    if (res == 1e9) res = -1;
    cout << res;
    return 0;
}

$\;\;\;\;$第二题,$Segment\;with\;the\;Required\;Subset$,题目大意:$n$个元素,找出一个最短的连续区间,使得存在一个子集,子集和为$s$$(n<=10^5\;s<=1000)$。容易发现是区间可行性背包问题,可以使用$bitset$优化,使用对顶栈,复杂度瓶颈在于$check$,枚举一个栈顶的可行性,判断另一个栈顶是否具有另一半的可行性即可。复杂度$O(ns)$,小常数可过。

#include <iostream>
#include <bitset>

using namespace std;

const int N = 100010, M = 1010;

int n, m;
int a[N];

struct Stack {
    int stk[N];
    bitset<M> f[N];
    int tt;
    void init() {
        f[0].set(0);
    }
    void push(int x) {
        ++tt;
        stk[tt] = x;
        f[tt] = f[tt - 1] | (f[tt - 1] << x);
    }
    int pop() {
        return stk[tt--];
    }
    bool empty() {
        return !tt;
    }
};

struct AdjointStack {
    Stack s1, s2;
    AdjointStack() {
        s1.init();
        s2.init();
    }
    void push(int x) {
        s2.push(x);
    }
    void pop() {
        if (s1.empty())
            while (!s2.empty())
                s1.push(s2.pop());
        s1.pop();
    }
    bool check() {
        for (int i = 0; i <= m / 2; i++) {
            if (s1.f[s1.tt].test(i) && s2.f[s2.tt].test(m - i)) return true;
            if (s1.f[s1.tt].test(m - i) && s2.f[s2.tt].test(i)) return true;
        }
        return false;
    }
}s;

int main() {
    cin >> n >> m;
    int res = 1e9;
    for (int i = 1, j = 1; i <= n; i++) {
        cin >> a[i];
        s.push(a[i]);
        while (j <= i && s.check()) {
            res = min(res, i - j + 1);
            s.pop();
            j++;
        }
    }
    if (res == 1e9) res = -1;
    cout << res;
    return 0;
}

$\;\;\;\;$第三题,$Link\;with\;Level\;Editor\;II$,题目大意:有$n$组边集,$m$个点,选出一段连续边集,初始在$1$号点,按顺序通过每个边集中的边(或原地不动直接跳过这组边集),使得从$1$号点到$m$号点的方案数不超过$k$。转化问题,把边集视作转移矩阵,求最长连续段矩阵,其连乘积的$mat[1][m]$不超过$k$。显然双指针,不方便移动左指针,如果使用线段树$/st表$显然容易超时,考虑使用对顶栈,注意这里矩阵左右乘有别,从插入栈挪到删除栈时需左乘,因为这个问题我调了一下午三个多小时。

#include <iostream>
#include <cstring>

using namespace std;

const int M = 20;
const int N = 5010;

using i64 = long long;

int n, m, k;

void add(int& x, i64 v) {
    if (v > k) v = k;
    x += v;
    if (x > k) x = k;
}

struct Matrix {
    int v[M][M];
    void init(int t = 0) {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                v[i][j] = 0;
        if (t)
            for (int i = 0; i < m; i++)
                v[i][i] = 1;
    }
    Matrix operator* (const Matrix& b) {
        Matrix res;
        res.init(0);
        for (int i = 0; i < m; i++)
            for (int j = 0; j < m; j++)
                for (int k = 0; k < m; k++)
                    add(res.v[i][j], 1ll * v[i][k] * b.v[k][j]);
        return res;
    }
    int operator& (const Matrix& b) {
        int res = 0;
        for (int k = 0; k < m; k++)
            add(res, 1ll * v[0][k] * b.v[k][m - 1]);
        return res;
    }
}mat[N];

struct Stack {
    int stk[N], tt;
    Matrix prod[N];
    void init() {
        prod[tt = 0].init(1);
    }
    void push(int x, int t = 0) {
        tt++;
        stk[tt] = x;
        if (t == 1) prod[tt] = prod[tt - 1] * mat[stk[tt]];
        else prod[tt] = mat[stk[tt]] * prod[tt - 1];
    }
    int pop() {
        return stk[tt--];
    }
    bool empty() {
        return !tt;
    }
};

struct AdjointStack {
    Stack s1, s2;
    void clear() {
        s1.init();
        s2.init();
    }
    void push(int x) {
        s2.push(x, 1);
    }
    void pop() {
        if (s1.empty())
            while (!s2.empty())
                s1.push(s2.pop());
        s1.pop();
    }
    bool check() {
        int res = s1.prod[s1.tt] & s2.prod[s2.tt];
        return res < k;
    }
}s;

void solve() {
    scanf("%d%d%d", &n, &m, &k);
    ++k;
    int res = 0;
    s.clear();
    for (int i = 1; i <= n; i++) {
        mat[i].init(1);
        int l;
        scanf("%d", &l);
        while (l--) {
            int u, v;
            scanf("%d%d", &u, &v);
            mat[i].v[--u][--v] = 1;
        }
    }
    for (int i = 1, j = 1; i <= n; i++) {
        s.push(i);
        while (j <= i && !s.check()) s.pop(), j++;
        res = max(res, i - j + 1);
    }
    printf("%d\n", res);
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}



用半平面交求出瞭望塔顶可以存在的区域的轮廓。

猜得最优解一定在下半边顶点向上引射线和上半边的交点或上半边顶点向下引射线和下半边的交点上。

于是枚举取最小距离即可。

为了方便可以在无穷远处添加三条直线圈出边界。

吐槽:寄算几何真难写 很简单的思路写起代码来也要命

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 10010;
const double eps = 1e-12;
const double INF = 1e18;

int sign(double x) {
    if (fabs(x) <= eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int cmp(double x, double y) {
    if (fabs(x - y) <= eps) return 0;
    if (x < y) return -1;
    return 1;
}

struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    void read() { scanf("%lf%lf", &x, &y); }
    void print() { printf("x:%lf y:%lf\n", x, y); }
    bool operator== (const Point& b) const { return !cmp(x, b.x) && !cmp(y, b.y); }
    bool operator< (const Point& b) const { return y != b.y ? y < b.y : x < b.x; }
    Point operator+ (const Point& b) const { return {x + b.x, y + b.y}; }
    Point operator- (const Point& b) const { return {x - b.x, y - b.y}; }
    Point operator* (const double& b) const { return {x * b, y * b}; }
    Point operator/ (const double& b) const { return {x / b, y / b}; }
    double operator* (const Point& b) const { return x * b.y - y * b.x; }
    double operator& (const Point& b) const { return x * b.x + y * b.y; }
    double len2() { return *this & *this; }
    double len() { return sqrt(this->len2()); }
    Point rotate(double b) { return {x * cos(b) + y * sin(b), -x * sin(b) + y * cos(b)}; }
}a[N], p[N], null(INF, INF);
using Vector = Point;
struct Line {
    Point st, ed;
    Line() {}
    Line(Point a, Point b) : st(a), ed(b) {}
    double get_angle() { return atan2(ed.y - st.y, ed.x - st.x); }
}l[N];
int n;
int q[N];
int cnt;

double area(Point a, Point b, Point c) {
    return (b - a) * (c - a);
}

bool lcmp(Line& a, Line& b) {
    double A = a.get_angle(), B = b.get_angle();
    if (!cmp(A, B)) return area(a.st, a.ed, b.ed) < 0;
    return A < B;
}

bool on_segment(Point p, Point a, Point b) {
    return sign((p - a) & (p - b)) <= 0;
}

Point get_line_intersection(Point p, Vector v, Point q, Vector w) {
    Vector u = p - q;
    double t = (w * u) / (v * w);
    return p + v * t;
}

Point get_segment_intersection(Point p, Vector v, Point q, Vector w) {
    Point o = get_line_intersection(p, v, q, w);
    if (!on_segment(o, p, p + v) || !on_segment(o, q, q + w)) return null;
    return o;
}

bool on_right(Line& a, Line& b, Line& c) {
    Point o = get_line_intersection(b.st, b.ed - b.st, c.st, c.ed - c.st);
    return area(a.st, a.ed, o) <= 0;
}

void half_plane_intersection() {
    sort(l, l + cnt, lcmp);
    int hh = 0, tt = -1;
    for (int i = 0; i < cnt; i++) {
        if (i && !cmp(l[i - 1].get_angle(), l[i].get_angle())) continue;
        while (hh + 1 <= tt && on_right(l[i], l[q[tt - 1]], l[q[tt]])) tt--;
        while (hh + 1 <= tt && on_right(l[i], l[q[hh]], l[q[hh + 1]])) hh++;
        q[++tt] = i;
    }
    while (hh + 1 <= tt && on_right(l[q[hh]], l[q[tt - 1]], l[q[tt]])) tt--;
    while (hh + 1 <= tt && on_right(l[q[tt]], l[q[hh]], l[q[hh + 1]])) hh++;
    int k = 0;
    double res = INF;
    q[++tt] = q[hh];
    for (int i = hh; i < tt; i++)
        a[k++] = get_line_intersection(l[q[i]].st, l[q[i]].ed - l[q[i]].st, l[q[i + 1]].st, l[q[i + 1]].ed - l[q[i + 1]].st);
    sort(a, a + k);
    for (int i = 0; i < n; i++) {
        Point o = Point(p[i].x, INF);  
        for (int j = 0; j + 1 < k; j++) {
            Point w = get_segment_intersection(p[i], o - p[i], a[j], a[j + 1] - a[j]);
            if (w == null) continue;
            res = min(res, (w - p[i]).len());
        }
    }
    for (int i = 0; i < k; i++) {
        Point o = Point(a[i].x, -INF);  
        for (int j = 0; j + 1 < n; j++) {
            Point w = get_segment_intersection(a[i], o - a[i], p[j], p[j + 1] - p[j]);
            if (w == null) continue;
            res = min(res, (w - a[i]).len());
        }
    }
    printf("%.3lf\n", res);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%lf", &p[i].x);
    for (int i = 0; i < n; i++) scanf("%lf", &p[i].y);
    for (int i = 0; i < n - 1; i++)
        l[cnt++] = Line(p[i], p[i + 1]);
    l[cnt++] = Line(Point(-INF, INF), Point(-INF, -INF));
    l[cnt++] = Line(Point(INF, INF), Point(-INF, INF));
    l[cnt++] = Line(Point(INF, -INF), Point(INF, INF));
    half_plane_intersection();
    return 0;
}



题目链接

$Mike\;and\;Friends$

$Duff\;is\;Mad$

题目描述

这里把两题合在一起看。

给定 $n$ 个字符串 $s_{1 \dots n}$。
$q$ 次询问 $s_k$ 在 $s_{l \dots r}$ 中出现了多少次。
$n, \sum |s| \le 2 \times 10^5$,$q \le 5 \times 10^5$。

给定 $n$ 个字符串 $s_{1 \dots n}$。
$q$ 次询问 $s_{l \dots r}$ 在 $s_k$ 中出现了多少次。
$n,q,\sum_{i=1}^n |s_i| \le 10^5$。

解法

$\;\;\;\;\;\;\;$先看第一题,首先建立$ACAM$,先考虑单串包含次数怎么算,$S_i$在$S_j$里出现次数等价于$S_i$作为$S_j$前缀的后缀出现的次数,考虑$fail$指针的意义,一个结点$fail$链上的所有结点的代表字符串都是这个结点的代表字符串的后缀,所以一个结点的代表字符串一定是他$fail$树上的子树中的所有结点的代表字符串的后缀。

$\;\;\;\;\;\;\;$所以$S_i$是否作为$S_j$的后缀出现,只需要看$S_j$的终止结点是否在$S_i$在$fail$树上的子树内出现即可。那么作为子串出现次数的做法也显而易见了,对$S_j$的所有前缀进行单点标记$+1$,查询$S_i$终止结点在$fail$树上的子树和即可。那么对于区间询问,只需要以下标为版本建立$fail$树$dfs$序可持久化线段树,进行版本区间$+$子树区间和查询即可。

$\;\;\;\;\;\;\;$之后看第二题,虽然形式相似,但是好像延用上一题的做法没法做了,这里考虑根号分治,设阈值$T$,$\sum |s| = m$,对于$length$大于$T$的询问串$S_k$,显然这样的串不会超过$\frac{m}{T}$个,那么我们可以对于每个串进行暴力查询,具体做法为将$S_k$的所有前缀结点标记$+1$,然后将从$1$到$n$的终止节点的$fail$树的子树和累加前缀和,记为$sum_i$,对于一个询问$(l,r,k)$,他的答案即为$sum_r-sum_{l-1}$。注意这里不要用树状数组进行子树加单点查,因为对于每个长度大于阈值的串,这一批查询被打上标记的点的固定的,只需要单点加后一遍$dfs$累加子树和即可,否则会多一个$log$。这里的复杂度是$O(\frac{m}{T}*(m+n))$,即对于每个询问串,先进行一遍$dfs$,再扫描一遍所有串。

$\;\;\;\;\;\;\;$再考虑$length$不大于$T$的询问串,上面说过$S_i$是否作为$S_j$的后缀出现,只需要看$S_j$的终止结点是否在$S_i$在$fail$树上的子树内出现即可,那么其实$S_i$作为$S_j$子串出现的次数,实质上是统计子树与树链的交,前文做法是标记树链,查询子树和,那我们同样可以标记子树,查询树链和,于是可以将所有询问在一遍扫描中处理,具体做法即将每个询问拆成两个询问容斥,将$(id,k,sign)$挂在下标上,之后从$1$到$n$扫描所有串,每到一个位置的时候对这个串终止结点进行子树$+1$,之后处理这个位置的所有询问,即对询问串$S_k$暴力求$trie$上的树链和乘上$sign$累加到$ans[id]$即可。这部分的复杂度是$O(nlogm+qTlogm)$

$\;\;\;\;\;\;\;$考虑根号平衡,由均值不等式可知当$\frac{m}{T}*(m+n)=qTlogm$时时间复杂度最优,即$T=\sqrt{\frac{m^2+mn}{qlogm}}$,此时时间复杂度为$O(nlogm+\sqrt{qlogm * (m^2+mn)})$,约为$10^8$量级,$4s$可过。

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int N = 200010;

int n, m;
int cnt[N];
int tr[N][26], trie_idx;
int q[N], fail[N], id[N];
int e[N], ne[N], h[N], idx;
int L[N], R[N], ts;
string s;
struct Node {
    int l, r;
    int cnt;
}T[N << 5];
int root[N];
vector<int> ver[N];
int node[N];

void insert(int p, int& q, int l, int r, int x, int v) {
    q = ++idx;
    T[q] = T[p], T[q].cnt += v;
    if (l == r) return;
    int mid = l + r >> 1;
    if (x <= mid) insert(T[p].l, T[q].l, l, mid, x, v);
    else insert(T[p].r, T[q].r, mid + 1, r, x, v);
}

int query(int p, int q, int l, int r, int ql, int qr) {
    if (l >= ql && r <= qr) return T[q].cnt - T[p].cnt;
    int mid = l + r >> 1, res = 0;
    if (ql <= mid) res += query(T[p].l, T[q].l, l, mid, ql, qr);
    if (qr > mid) res += query(T[p].r, T[q].r, mid + 1, r, ql, qr);
    return res;
}

void insert(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void dfs(int u) {
    L[u] = ++ts;
    for (int i = h[u]; ~i; i = ne[i]) dfs(e[i]);
    R[u] = ts;
}

void insert(int id) {
    int p = 0;
    cin >> s;
    for (int i = 0; s[i]; i++) {
        int u = s[i] - 'a';
        if (!tr[p][u]) tr[p][u] = ++trie_idx;
        p = tr[p][u];     
        ver[id].push_back(p);
    }
    node[id] = p;
}

void build() {
    int tt = -1, hh = 0;
    for (int i = 0; i < 26; i++)
        if (tr[0][i])
            q[++tt] = tr[0][i];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = 0; i < 26; i++) {
            int& p = tr[t][i];
            if (!p) p = tr[fail[t]][i];
            else {
                fail[p] = tr[fail[t]][i];
                q[++tt] = p;
            }
        }
    }
}

int main() {
    cin.tie(0), cout.tie(0)->sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) insert(i);
    build();
    memset(h, -1, sizeof h);
    for (int i = 1; i <= trie_idx; i++) insert(fail[i], i);
    dfs(0);
    for (int i = 1; i <= n; i++) {
        root[i] = root[i - 1];
        for (auto item : ver[i]) 
            insert(root[i], root[i], 1, ts, L[item], 1);
    }
    while (m--) {
        int l, r, k;
        cin >> l >> r >> k;
        k = node[k];
        cout << query(root[l - 1], root[r], 1, ts, L[k], R[k]) << '\n';
    }
    return 0;
}

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;
using i64 = long long;

const int N = 100010, M = 100010;

struct Query {
    int a, b, c;
};
vector<Query> v1[N], v2[N];
int node_id[N], len[N], trie_idx;
i64 ans[N];
int tr[N][26];
int fail[N];
int e[M], ne[M], h[N], idx;
int l[N], r[N], ts;
int que[N];
int s[N];
i64 sum[N];
int fa[N];
int n, m, q;

struct BIT {
    int tr[N];
    inline int lowbit(int x) {
        return x & -x;
    }
    inline void add(int x, int v) {
        for (; x <= ts; x += lowbit(x))
            tr[x] += v;
    }
    inline void add(int l, int r, int v) {
        add(l, v);
        add(r + 1, -v);
    }
    inline int ask(int x) {
        int res = 0;
        for (; x; x -= lowbit(x))
            res += tr[x];
        return res;
    }
}t;

void insert(int u, int v) {
    e[idx] = v, ne[idx] = h[u], h[u] = idx++;
}

void insert(int id) {
    int p = 0;
    string s;
    cin >> s;
    for (int i = 0; s[i]; i++) {
        int c = s[i] - 'a';
        if (!tr[p][c]) tr[p][c] = ++trie_idx;
        fa[tr[p][c]] = p;
        p = tr[p][c];
    }
    node_id[id] = p;
    m += (len[id] = s.size());
}

void build() {
    int tt = -1, hh = 0;
    for (int i = 0; i < 26; i++)
        if (tr[0][i]) 
            que[++tt] = tr[0][i];
    while (hh <= tt) {
        int t = que[hh++];
        for (int i = 0; i < 26; i++) {
            int& p = tr[t][i];
            if (!p) p = tr[fail[t]][i];
            else {
                fail[p] = tr[fail[t]][i];
                que[++tt] = p;
            }
        }
    }
    memset(h, -1, sizeof h);
    for (int i = 1; i <= trie_idx; i++)
        insert(fail[i], i);
}

void dfs_sum(int u) {
    for (int i = h[u]; ~i; i = ne[i]) {
        dfs_sum(e[i]);
        s[u] += s[e[i]];
    }
}

void dfs(int u) {
    l[u] = ++ts;
    for (int i = h[u]; ~i; i = ne[i]) dfs(e[i]);
    r[u] = ts;
}

int main() {
    cin.tie(0)->sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) insert(i);
    int T = m / sqrt(q * log2(m));
    build();
    dfs(0);
    for (int i = 1; i <= q; i++) {
        int l, r, k;
        cin >> l >> r >> k;
        if (len[k] > T) v1[k].push_back({l, r, i});
        else {
            if (l > 1) v2[l - 1].push_back({k, i, -1});
            v2[r].push_back({k, i, 1});
        }
    }
    for (int i = 1; i <= n; i++) {
        if (len[i] > T) {
            if (v1[i].empty()) continue;
            for (int p = node_id[i]; p; p = fa[p]) s[p] = 1;
            dfs_sum(0);
            for (int j = 1; j <= n; j++) 
                sum[j] = sum[j - 1] + s[node_id[j]];
            for (auto& [l, r, id] : v1[i]) ans[id] = sum[r] - sum[l - 1];
            memset(sum, 0, (n + 5) * sizeof(int));
            memset(s, 0, (m + 5) * sizeof(int));
        }
    }
    for (int i = 1; i <= n; i++) {
        int u = node_id[i];
        t.add(l[u], r[u], 1);
        for (auto& [k, id, sign] : v2[i]) {
            for (int p = node_id[k]; p; p = fa[p]) 
                ans[id] += sign * t.ask(l[p]);
        }
    }
    for (int i = 1; i <= q; i++) cout << ans[i] << '\n';
    return 0;
}


活动打卡代码 AcWing 2938. 周游世界

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 50010;
const double eps = 1e-8;
const double INF = 1e9;

int sign(double x) {
    if (fabs(x) <= eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int cmp(double x, double y) {
    if (fabs(x - y) <= eps) return 0;
    if (x < y) return -1;
    return 1;
}

struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    void read() { scanf("%lf%lf", &x, &y); }
    void print() { printf("x:%lf y:%lf\n", x, y); }
    bool operator< (const Point& b) const { return y != b.y ? y < b.y : x < b.x; }
    Point operator+ (const Point& b) const { return {x + b.x, y + b.y}; }
    Point operator- (const Point& b) const { return {x - b.x, y - b.y}; }
    Point operator* (const double& b) const { return {x * b, y * b}; }
    Point operator/ (const double& b) const { return {x / b, y / b}; }
    double operator* (const Point& b) const { return x * b.y - y * b.x; }
    double operator& (const Point& b) const { return x * b.x + y * b.y; }
    double len2() { return *this & *this; }
    double len() { return sqrt(*this & *this); }
    Point rotate(double b) { return {x * cos(b) + y * sin(b), -x * sin(b) + y * cos(b)}; }
}q[N];
using Vector = Point;
int stk[N];
int top;
int n;

double area(Point a, Point b, Point c) {
    return (b - a) * (c - a);
}

void get_convex() {
    sort(q, q + n);
    for (int i = 0; i < n; i++) {
        while (top > 1 && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) top--;
        stk[++top] = i;
    }
    int k = top;
    for (int i = n - 1; ~i; i--) {
        while (top > k && area(q[stk[top - 1]], q[stk[top]], q[i]) <= 0) top--;
        stk[++top] = i;
    }
}

int rotating_calipers() {
    int res = 0;
    for (int i = 1, j = 3; i < top; i++) {
        Point a = q[stk[i]], b = q[stk[i + 1]];
        while (area(a, b, q[stk[j]]) < area(a, b, q[stk[j + 1]])) {
            j = j + 1;
            if (j == top + 1) j = 1;
        }
        res = max(res, (int) max((q[stk[j]] - a).len2(), (q[stk[j]] - b).len2()));
    }
    return res;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) q[i].read();
    get_convex();
    printf("%d\n", rotating_calipers());
    return 0;
}


活动打卡代码 AcWing 206. 石头游戏

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;
const int dir[][2] = {-1, 0, 0, -1, 1, 0, 0, 1}; // NWSE

using i64 = long long;

int n, m, t, q;
char s[N][N], p[N][N];
int len[N];
int tot;
int mp[500];

struct Matrix {
    i64 v[N][N];
    Matrix(int t = 0) {
        memset(v, 0, sizeof v);
        if (!t) {
            for (int i = 0; i <= tot; i++)
                v[i][i] = 1;
        }
    }
    Matrix operator* (const Matrix& b) const {
        Matrix res(1);
        for (int i = 0; i <= tot; i++)
            for (int j = 0; j <= tot; j++)
                for (int k = 0; k <= tot; k++)
                    res.v[i][j] += v[i][k] * b.v[k][j];
        return res;
    }
    Matrix operator^ (int b) const {
        Matrix res, a = *this;
        while (b) {
            if (b & 1) res = res * a;
            a = a * a;
            b >>= 1;
        }
        return res;
    }
}trans[N];

int get(int i, int j) {
    return i * m + j;     
}

int main() {
    mp['N'] = 0, mp['W'] = 1, mp['S'] = 2, mp['E'] = 3;
    cin >> n >> m >> t >> q;
    tot = n * m;
    for (int i = 0; i < n; i++) cin >> s[i];
    for (int i = 0; i < q; i++) {
        cin >> p[i];
        len[i] = strlen(p[i]);
    }
    for (int t = 0; t < 60; t++) {
        trans[t] = Matrix();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int type = s[i][j] - '0', id = get(i, j);
                char op = p[type][t % len[type]];
                if (isdigit(op)) trans[t].v[tot][id] = op - '0'; 
                else if (op == 'D') trans[t].v[id][id] = 0; 
                else {
                    int d = mp[op];
                    int tx = i + dir[d][0], ty = j + dir[d][1];
                    if (tx >= 0 && tx < n && ty >= 0 && ty < m) 
                        trans[t].v[id][get(tx, ty)] = 1;
                    trans[t].v[id][id] = 0;
                }
            }
        }
        if (t) trans[t] = trans[t - 1] * trans[t];
    }
    Matrix mat(1);
    mat.v[0][tot] = 1;
    mat = mat * (trans[59] ^ t / 60) * (t % 60 ? trans[t % 60 - 1] : Matrix());
    cout << *max_element(mat.v[0], mat.v[0] + tot);
    return 0;
}



刚学完趁热打个铁
显然的半平面交板子题
因为要线段露出才算看到 所以点在直线上也要弹出 封口的时候要注意条件
不然如果半平面交只有两条直线的话会误弹在半平面交上的点

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 50010;
const double eps = 1e-12;
const double INF = 1e9;

int sign(double x) {
    if (fabs(x) <= eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int cmp(double x, double y) {
    if (fabs(x - y) <= eps) return 0;
    if (x < y) return -1;
    return 1;
}

struct Point {
    double x, y;
    int id;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    // void read() { scanf("%d%Lf%Lf", &id, &x, &y); }
    // void print() { printf("x:%lf y:%lf\n", x, y); }
    bool operator< (const Point& b) const { return y != b.y ? y < b.y : x < b.x; }
    Point operator+ (const Point& b) const { return {x + b.x, y + b.y}; }
    Point operator- (const Point& b) const { return {x - b.x, y - b.y}; }
    Point operator* (const double& b) const { return {x * b, y * b}; }
    Point operator/ (const double& b) const { return {x / b, y / b}; }
    double operator* (const Point& b) const { return x * b.y - y * b.x; }
    double operator& (const Point& b) const { return x * b.x + y * b.y; }
    double len() { return sqrt(*this & *this); }
    Point rotate(double b) { return {x * cos(b) + y * sin(b), -x * sin(b) + y * cos(b)}; }
};
using Vector = Point;
struct Line {
    Point st, ed;
    int id;
    Line() {}
    Line(Point a, Point b, int i) : st(a), ed(b), id(i) {}
    vector<int> ids;
    double get_angle() { return atan2(ed.y - st.y, ed.x - st.x); }
}l[N];
int q[N];
int n;

double area(Point a, Point b, Point c) {
    return (b - a) * (c - a);
}

bool lcmp(Line& a, Line& b) {
    double A = a.get_angle(), B = b.get_angle();
    if (!cmp(A, B)) return area(a.st, a.ed, b.ed) < 0; // 极角相同 靠左的在前面
    return A < B;
}

Point get_line_intersection(Point p, Vector v, Point q, Vector w) {
    Vector u = p - q;
    double t = (w * u) / (v * w);
    return p + v * t;
}

// b、c交点是否在a右侧
bool on_right(Line& a, Line& b, Line& c) {
    Point o = get_line_intersection(b.st, b.ed - b.st, c.st, c.ed - c.st);
    return area(a.st, a.ed, o) <= 0;
}

void half_plane_intersection() {
    sort(l, l + n, lcmp);
    int hh = 0, tt = -1;
    for (int i = 0; i < n; i++) {
        if (i && !cmp(l[i - 1].get_angle(), l[i].get_angle())) continue;
        while (hh + 1 <= tt && on_right(l[i], l[q[tt - 1]], l[q[tt]])) tt--;
        while (hh + 1 <= tt && on_right(l[i], l[q[hh]], l[q[hh + 1]])) hh++;
        q[++tt] = i;
    }
    while (hh + 2 <= tt && on_right(l[q[hh]], l[q[tt - 1]], l[q[tt]])) tt--;
    while (hh + 2 <= tt && on_right(l[q[tt]], l[q[hh]], l[q[hh + 1]])) hh++; 
    vector<int> ans;
    for (int i = hh; i <= tt; i++) ans.push_back(l[q[i]].id);
    sort(ans.begin(), ans.end());
    for (auto item : ans) printf("%d ", item);
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int k, b;
        scanf("%d%d", &k, &b);
        l[i] = Line(Point(0, b), Point(1, k + b), i + 1);
    }
    half_plane_intersection();
    return 0;
}


活动打卡代码 AcWing 2803. 凸多边形

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>

using namespace std;

const int N = 10010;
const double eps = 1e-8;
const double INF = 1e9;

int sign(double x) {
    if (fabs(x) <= eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int cmp(double x, double y) {
    if (fabs(x - y) <= eps) return 0;
    if (x < y) return -1;
    return 1;
}

struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    void read() { scanf("%lf%lf", &x, &y); }
    void print() { printf("x:%lf y:%lf\n", x, y); }
    bool operator< (const Point& b) const { return y != b.y ? y < b.y : x < b.x; }
    Point operator+ (const Point& b) const { return {x + b.x, y + b.y}; }
    Point operator- (const Point& b) const { return {x - b.x, y - b.y}; }
    Point operator* (const double& b) const { return {x * b, y * b}; }
    Point operator/ (const double& b) const { return {x / b, y / b}; }
    double operator* (const Point& b) const { return x * b.y - y * b.x; }
    double operator& (const Point& b) const { return x * b.x + y * b.y; }
    double len() { return sqrt(*this & *this); }
    Point rotate(double b) { return {x * cos(b) + y * sin(b), -x * sin(b) + y * cos(b)}; }
}p[N];
using Vector = Point;
struct Line {
    Point st, ed;
    Line() {}
    Line(Point a, Point b) : st(a), ed(b) {}
    double get_angle() { return atan2(ed.y - st.y, ed.x - st.x); }
}l[N];
int q[N];
int vi[N], ki[N];
int n, cnt;

double area(Point a, Point b, Point c) {
    return (b - a) * (c - a);
}

bool lcmp(Line& a, Line& b) {
    double A = a.get_angle(), B = b.get_angle();
    if (!cmp(A, B)) return area(a.st, a.ed, b.ed) < 0; // 极角相同 靠左的在前面
    return A < B;
}

Point get_line_intersection(Point p, Vector v, Point q, Vector w) {
    Vector u = p - q;
    double t = (w * u) / (v * w);
    return p + v * t;
}

// b、c交点是否在a右侧
bool on_right(Line& a, Line& b, Line& c) {
    Point o = get_line_intersection(b.st, b.ed - b.st, c.st, c.ed - c.st);
    return area(a.st, a.ed, o) <= 0;
}

double half_plane_intersection() {
    sort(l, l + cnt, lcmp);
    int hh = 0, tt = -1;
    for (int i = 0; i < cnt; i++) {
        if (i && !cmp(l[i - 1].get_angle(), l[i].get_angle())) continue;
        while (hh + 1 <= tt && on_right(l[i], l[q[tt - 1]], l[q[tt]])) tt--;
        while (hh + 1 <= tt && on_right(l[i], l[q[hh]], l[q[hh + 1]])) hh++;
        q[++tt] = i;
    }
    while (hh + 1 <= tt && on_right(l[q[hh]], l[q[tt - 1]], l[q[tt]])) tt--;
    while (hh + 1 <= tt && on_right(l[q[tt]], l[q[hh]], l[q[hh + 1]])) hh++;
    int k = 0;
    q[++tt] = q[hh];
    for (int i = hh; i < tt; i++)
        p[k++] = get_line_intersection(l[q[i]].st, l[q[i]].ed - l[q[i]].st, l[q[i + 1]].st, l[q[i + 1]].ed - l[q[i + 1]].st);
    double res = 0;
    for (int i = 1; i + 1 < k; i++)
        res += area(p[0], p[i], p[i + 1]);
    return res / 2;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int m;
        scanf("%d", &m);
        for (int j = 0; j < m; j++) p[j].read();
        for (int j = 0; j < m; j++) l[cnt++] = Line(p[j], p[(j + 1) % m]);
    }
    printf("%.3lf\n", half_plane_intersection());
    return 0;
}


活动打卡代码 AcWing 2957. 赛车

好像懂了
又好像没懂

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <map>

#define double long double

using namespace std;

const int N = 10010;
const double eps = 1e-18;
const double INF = 1e9;

int sign(double x) {
    if (fabs(x) <= eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int cmp(double x, double y) {
    if (fabs(x - y) <= eps) return 0;
    if (x < y) return -1;
    return 1;
}

struct Point {
    double x, y;
    int id;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    // void read() { scanf("%d%Lf%Lf", &id, &x, &y); }
    // void print() { printf("x:%lf y:%lf\n", x, y); }
    bool operator< (const Point& b) const { return y != b.y ? y < b.y : x < b.x; }
    Point operator+ (const Point& b) const { return {x + b.x, y + b.y}; }
    Point operator- (const Point& b) const { return {x - b.x, y - b.y}; }
    Point operator* (const double& b) const { return {x * b, y * b}; }
    Point operator/ (const double& b) const { return {x / b, y / b}; }
    double operator* (const Point& b) const { return x * b.y - y * b.x; }
    double operator& (const Point& b) const { return x * b.x + y * b.y; }
    double len() { return sqrt(*this & *this); }
    Point rotate(double b) { return {x * cos(b) + y * sin(b), -x * sin(b) + y * cos(b)}; }
};
using Vector = Point;
struct Line {
    Point st, ed;
    Line() {}
    Line(Point a, Point b, vector<int> v = vector<int>()) : st(a), ed(b), ids(v) {}
    vector<int> ids;
    double get_angle() { return atan2(ed.y - st.y, ed.x - st.x); }
}l[N];
int q[N];
int vi[N], ki[N];
int n, cnt;

double area(Point a, Point b, Point c) {
    return (b - a) * (c - a);
}

bool lcmp(Line& a, Line& b) {
    double A = a.get_angle(), B = b.get_angle();
    if (!cmp(A, B)) return area(a.st, a.ed, b.ed) < 0; // 极角相同 靠左的在前面
    return A < B;
}

Point get_line_intersection(Point p, Vector v, Point q, Vector w) {
    Vector u = p - q;
    double t = (w * u) / (v * w);
    return p + v * t;
}

// b、c交点是否在a右侧
bool on_right(Line& a, Line& b, Line& c) {
    Point o = get_line_intersection(b.st, b.ed - b.st, c.st, c.ed - c.st);
    return area(a.st, a.ed, o) < 0;
}

void half_plane_intersection() {
    sort(l, l + cnt, lcmp);
    int hh = 0, tt = -1;
    for (int i = 0; i < cnt; i++) {
        if (i && !cmp(l[i - 1].get_angle(), l[i].get_angle())) continue;
        while (hh + 1 <= tt && on_right(l[i], l[q[tt - 1]], l[q[tt]])) tt--;
        while (hh + 1 <= tt && on_right(l[i], l[q[hh]], l[q[hh + 1]])) hh++;
        q[++tt] = i;
    }
    while (hh + 1 <= tt && on_right(l[q[hh]], l[q[tt - 1]], l[q[tt]])) tt--;
    while (hh + 1 <= tt && on_right(l[q[tt]], l[q[hh]], l[q[hh + 1]])) hh++;
    vector<int> ans;
    for (int i = hh; i <= tt; i++)
        for (auto id : l[q[i]].ids)
            ans.push_back(id);
    sort(ans.begin(), ans.end());
    printf("%d\n", (int) ans.size());
    for (auto item : ans) printf("%d ", item);
}

int main() {
    map<pair<int, int>, vector<int>> ids;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", ki + i);
    for (int i = 1; i <= n; i++) scanf("%d", vi + i);
    for (int i = 1; i <= n; i++)
        ids[{ki[i], vi[i]}].push_back(i);
    l[cnt++] = Line(Point(0, 10000), Point(0, 0));
    l[cnt++] = Line(Point(0, 0), Point(10000, 0));
    for (auto& [k, vec] : ids)
        l[cnt++] = Line(Point(0, k.first), Point(1, k.first + k.second), vec);
    half_plane_intersection();
    return 0;
}


活动打卡代码 AcWing 4569. 太空蚂蚁

不是很懂

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 110;
const double eps = 1e-12;
const double INF = 1e9;

int sign(double x) {
    if (fabs(x) <= eps) return 0;
    if (x < 0) return -1;
    return 1;
}

int cmp(double x, double y) {
    if (fabs(x - y) <= eps) return 0;
    if (x < y) return -1;
    return 1;
}

struct Point {
    double x, y;
    int id;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) {}
    void read() { scanf("%d%lf%lf", &id, &x, &y); }
    void print() { printf("x:%lf y:%lf\n", x, y); }
    bool operator< (const Point& b) const { return y != b.y ? y < b.y : x < b.x; }
    Point operator+ (const Point& b) const { return {x + b.x, y + b.y}; }
    Point operator- (const Point& b) const { return {x - b.x, y - b.y}; }
    Point operator* (const double& b) const { return {x * b, y * b}; }
    Point operator/ (const double& b) const { return {x / b, y / b}; }
    double operator* (const Point& b) const { return x * b.y - y * b.x; }
    double operator& (const Point& b) const { return x * b.x + y * b.y; }
    double len() { return sqrt(*this & *this); }
    Point rotate(double b) { return {x * cos(b) + y * sin(b), -x * sin(b) + y * cos(b)}; }
}q[N];

struct Line {
    Point a, b;
    Line() {}
    Line(Point _a, Point _b) : a(_a), b(_b) {}
}l[N];
using Vector = Point;
int n;
bool vis[N];
int cnt;

void solve() {
    memset(vis, false, sizeof vis);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) q[i].read();
    sort(q, q + n);
    printf("%d %d ", n, q[0].id);
    vis[0] = true;
    cnt = 0;
    l[++cnt] = Line(Point(0, q[0].y), q[0]);
    for (int t = 1; t < n; t++) {
        int res = 0;
        double mx = -1e9;
        Point a = l[cnt].a, b = l[cnt].b;
        for (int j = 0; j < n; j++) {
            if (vis[j]) continue;
            if (sign((b - a) * (q[j] - b)) < 0) continue;
            else {
                double cur = ((q[j] - b) & (b - a)) / (b - a).len() / (q[j] - b).len(); // cosθ越大 夹角越小
                if (cmp(cur, mx) > 0) mx = cur, res = j;
                else if (!cmp(cur, mx)) {
                    if ((q[res] - b).len() > (q[j] - b).len()) res = j;
                }
            }                
        }
        l[++cnt] = Line(b, q[res]);
        vis[res] = true;
        printf("%d ", q[res].id);
    }
    puts("");
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) solve();
}



最近学了计算几何,把这道缝合怪写一下。(调了很久,太菜了。)

将序列看成向量的序列,首先不考虑镜像操作,一段序列能和模板串匹配,那么图形必定相似,也就是说相邻两元素(向量)的模长之比和夹角必定相同,模长之比可以直接不开根,没有精度问题,但角度如果存$double$会有精度问题,于是应用下面的式子,存储夹角的正切,分子分母必定都是整数,这样就解决了精度问题。


$\frac{\vec{a} * \vec{b}} {|\vec{a}|·|\vec{b}|} = sinθ$

$\frac{\vec{a} · \vec{b}} {|\vec{a}|·|\vec{b}|} = cosθ$

$\frac{\vec{a} * \vec{b}} {\vec{a} · \vec{b}} = tanθ$


于是对于向量对$<$$\vec{u_i},\vec{u_{i+1}}$$>$,存储化为最简比的四元组$(|\vec{u_i}|,|\vec{u_{i+1}}|,\vec{u_i}\times\vec{u_{i+1}},\vec{u_i}·\vec{u_{i+1}})$作为向量间关系,若两个向量序列匹配,则他们的四元组序列也必匹配,于是对所有模式串(询问序列)的四元组建立$ACAM$,字符集用$map$存储,之后用模板串在上面跑一遍,标记所有经过的结点,在$fail$树上做树形$dp$累加标记,具体实现则直接用$bfs$中队列存储顺序的逆序做递推即可。


接下来考虑镜像操作,若一个操作序列不是所有点共线,则他镜像之后对应的$trie$树结点在$fail$树上的子树必定和镜像前没有交集(这句话好像是对的吧我也不知道对不对谔谔),而如果所有点共线,镜像之后匹配的结点必定和镜像前是同一个。由于镜像是相对的,对模板串镜像和对模式串镜像本质相同,所以有两种方法,第一种是建立$ACAM$时就将模式串的镜像也加入$ACAM$,记录一下每个串镜像前后匹配到的结点,之后跑一遍匹配,若镜像前后结点不同则将两个结点的$cnt$累加作为答案,第二种是建立$ACAM$时不加入镜像串,但记录模式串是否完全共线,即是否相邻元素的叉积全为零,匹配时将模板串镜像之后再跑一遍匹配,之后累加$cnt$,对共线的串答案除以二。由于方法一$ACAM$结点数较多,会慢一些。另外长度是$1$和$2$的序列在任何位置都能匹配,直接特判即可。


$Code$

方法一

#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>

using namespace std;

const int N = 200010;

struct Point {
    double x, y;
    Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
    void read() { scanf("%lf%lf", &x, &y); }
    void print() { printf("x:%lf y:%lf\n", x, y); }
    Point operator+ (const Point& b) const { return {x + b.x, y + b.y}; }
    Point operator- (const Point& b) const { return {x - b.x, y - b.y}; }
    Point operator* (const double& b) const { return {x * b, y * b}; }
    Point operator/ (const double& b) const { return {x / b, y / b}; }
    double operator* (const Point& b) const { return x * b.y - y * b.x; }
    double operator& (const Point& b) const { return x * b.x + y * b.y; }
    double len() { return sqrt(*this & *this); }
    double len2() { return *this & *this; }
    Point rotate(double b) { return {x * cos(b) + y * sin(b), -x * sin(b) + y * cos(b)}; }
}q[N];
using Vector = Point;

struct Node {
    int len1, len2; 
    int cross, dot;
    bool operator< (const Node& other) const {
        if (len1 ^ other.len1) return len1 < other.len1;
        if (len2 ^ other.len2) return len2 < other.len2;
        if (cross ^ other.cross) return cross < other.cross;
        return dot < other.dot;
    }
}t[N];

Node calc(Point a, Point b, Point c) {
    Vector u = b - a, v = c - b;
    int len1 = u.len2(), len2 = v.len2(), d1 = __gcd(len1, len2);
    int cross = u * v, dot = u & v, d2 = __gcd(abs(cross), abs(dot));
    return {len1 / d1, len2 / d1, cross / d2, dot / d2};
}

int n, m;
map<Node, int> tr[N];
using iter = map<Node, int>::iterator;
int fail[N], idx;
int k[N];
int node[N];
int que[N];
int cnt[N];

int insert(int n) {
    int p = 0;
    for (int i = 1; i <= n; i++) {
        if (!tr[p].count(t[i])) tr[p][t[i]] = ++idx;
        p = tr[p][t[i]];
    }
    return p;
}

void build() {
    int tt = -1, hh = 0;
    for (iter it = tr[0].begin(); it != tr[0].end(); it++)
        que[++tt] = it->second;
    while (hh <= tt) {
        int t = que[hh++];
        for (iter it = tr[t].begin(); it != tr[t].end(); it++) {
            int j = fail[t];
            while (j && !tr[j].count(it->first)) j = fail[j];
            if (tr[j].count(it->first)) j = tr[j][it->first];
            fail[it->second] = j;
            que[++tt] = it->second;
        }
    }
}

void run() {
    for (int i = 1; i <= n; i++) q[i].read();
    for (int i = 1; i + 2 <= n; i++) 
        t[i] = calc(q[i], q[i + 1], q[i + 2]);
    int p = 0;
    for (int i = 1; i + 2 <= n; i++) {
        while (p && !tr[p].count(t[i])) p = fail[p];
        if (tr[p].count(t[i])) p = tr[p][t[i]];
        cnt[p]++;
    }
    for (int i = idx; ~i; i--) cnt[fail[que[i]]] += cnt[que[i]];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", k + i);
        for (int j = 1; j <= k[i]; j++) q[j].read(); 
        if (k[i] <= 2) continue;
        for (int j = 1; j + 2 <= k[i]; j++) 
            t[j] = calc(q[j], q[j + 1], q[j + 2]);
        node[i] = insert(k[i] - 2);
        for (int j = 1; j <= k[i]; j++) q[j].y = -q[j].y;
        for (int j = 1; j + 2 <= k[i]; j++)
            t[j] = calc(q[j], q[j + 1], q[j + 2]);
        node[i + m] = insert(k[i] - 2);
    }
    build();
    run();
    for (int i = 1; i <= m; i++) {
        if (k[i] <= 2) cout << n - k[i] + 1 << '\n';
        else if (node[i] != node[i + m]) cout << cnt[node[i]] + cnt[node[i + m]] << '\n';
        else cout << cnt[node[i]] << '\n';
    }
    return 0;
}

方法二

#include <iostream>
#include <cstring>
#include <cmath>
#include <map>
#include <algorithm>

using namespace std;

const int N = 200010;

struct Point {
    double x, y;
    Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
    void read() { scanf("%lf%lf", &x, &y); }
    void print() { printf("x:%lf y:%lf\n", x, y); }
    Point operator+ (const Point& b) const { return {x + b.x, y + b.y}; }
    Point operator- (const Point& b) const { return {x - b.x, y - b.y}; }
    Point operator* (const double& b) const { return {x * b, y * b}; }
    Point operator/ (const double& b) const { return {x / b, y / b}; }
    double operator* (const Point& b) const { return x * b.y - y * b.x; }
    double operator& (const Point& b) const { return x * b.x + y * b.y; }
    double len() { return sqrt(*this & *this); }
    double len2() { return *this & *this; }
    Point rotate(double b) { return {x * cos(b) + y * sin(b), -x * sin(b) + y * cos(b)}; }
}q[N];
using Vector = Point;

struct Node {
    int len1, len2; 
    int cross, dot;
    bool operator< (const Node& other) const {
        if (len1 ^ other.len1) return len1 < other.len1;
        if (len2 ^ other.len2) return len2 < other.len2;
        if (cross ^ other.cross) return cross < other.cross;
        return dot < other.dot;
    }
}t[N];

Node calc(Point a, Point b, Point c) {
    Vector u = b - a, v = c - b;
    int len1 = u.len2(), len2 = v.len2(), d1 = __gcd(len1, len2);
    int cross = u * v, dot = u & v, d2 = __gcd(abs(cross), abs(dot));
    return {len1 / d1, len2 / d1, cross / d2, dot / d2};
}

int n, m;
map<Node, int> tr[N];
using iter = map<Node, int>::iterator;
int fail[N], idx;
int k[N];
int node[N];
int que[N];
int cnt[N];
int ans[N];
bool on_line[N];
int fa[N];

int insert(int n) {
    int p = 0;
    for (int i = 1; i <= n; i++) {
        if (!tr[p].count(t[i])) tr[p][t[i]] = ++idx;
        p = tr[p][t[i]];
    }
    return p;
}

void build() {
    int tt = -1, hh = 0;
    for (iter it = tr[0].begin(); it != tr[0].end(); it++)
        que[++tt] = it->second;
    while (hh <= tt) {
        int t = que[hh++];
        for (iter it = tr[t].begin(); it != tr[t].end(); it++) {
            int j = fail[t];
            while (j && !tr[j].count(it->first)) j = fail[j];
            if (tr[j].count(it->first)) j = tr[j][it->first];
            fail[it->second] = j;
            que[++tt] = it->second;
        }
    }
}

void run() {
    for (int i = 1; i <= n; i++) q[i].read();
    for (int i = 1; i + 2 <= n; i++) 
        t[i] = calc(q[i], q[i + 1], q[i + 2]);
    int p = 0;
    for (int i = 1; i + 2 <= n; i++) {
        while (p && !tr[p].count(t[i])) p = fail[p];
        if (tr[p].count(t[i])) p = tr[p][t[i]];
        cnt[p]++;
    }
    p = 0;
    for (int i = 1; i <= n; i++) q[i].y = -q[i].y;
    for (int i = 1; i + 2 <= n; i++)
        t[i] = calc(q[i], q[i + 1], q[i + 2]);
    for (int i = 1; i + 2 <= n; i++) {
        while (p && !tr[p].count(t[i])) p = fail[p];
        if (tr[p].count(t[i])) p = tr[p][t[i]];
        cnt[p]++;
    }
    for (int i = idx; ~i; i--) cnt[fail[que[i]]] += cnt[que[i]];
    for (int i = 1; i <= m; i++)
        ans[i] = cnt[node[i]] / (1 + on_line[i]);
}

int main() {
    scanf("%d%d", &n, &m);
    memset(on_line, true, sizeof on_line);
    for (int i = 1; i <= m; i++) {
        scanf("%d", k + i);
        for (int j = 1; j <= k[i]; j++) q[j].read(); 
        if (k[i] <= 2) continue;
        for (int j = 1; j + 2 <= k[i]; j++) {
            t[j] = calc(q[j], q[j + 1], q[j + 2]);
            if (t[j].cross) on_line[i] = false;
        }
        node[i] = insert(k[i] - 2);
    }
    build();
    run();
    for (int i = 1; i <= m; i++) {
        if (k[i] <= 2) cout << n - k[i] + 1 << '\n';
        else cout << ans[i] << '\n';
    }
    return 0;
}