Dyd's Blog

He who has a strong enough why can bear almost any how.

luoguP8000 [WFOI - 01] 循环节（circle）

Posted on In
Symbols count in article: 3.7k Reading time ≈ 3 mins.

利用平行转化为旋转卡壳 + 分讨

循环节（circle）

思路

拿到题觉得不可做，但这个时候就是要迎难而（男儿）上

考虑到 $a$ 中点是由 $b$ 多次平移得到，那么对于 $p, q \in b$ ， $(p \to p + x)$ 和 $(q \to q +x)$ 一定平行（或共线），又注意到 $b$ 中任意 $4$ 点四点不构成梯形或平行四边形，就是说 $b$ 中没有平行线，那么我们得到 $a$ 中的平行线一定是由平移得到的；但我们不可能把所有平行线找到，换个角度，我们直接做个凸包，不管内部的点，直管外部的平行线，显然这不会影响答案，因为凸包上的点平移过程一定是完整的

而找平行线可以旋转卡壳，具体的，当我们扫到边 $(i, i + 1)$ 时，把所有在对面那条平行线上的点取出来，记它们为 $[l, r]$ ，这条线上一定包含了至少一个完整的平移

现在想如何求这个平移，考虑到 $b$ 中任意三点不共线且题目保证平移过程中没有重点，大力分讨：

  • 只有一个点，搞个寂寞
  • 有两个点，当然是前面的点平移成为后面的点
  • 有 $\ge 3$ 个点
    1. 有一个点属于 $b$ （显然这个点是 $l$ ），其它点由它平移得到
    2. 有两个点属于 $b$ （显然有一个是 $l$ ，另一个记为 $st2$ ），且 $l$ 和 $st2$ 之间还有点（这些点显然由 $l$ 平移得到，可以帮我们确定 $x$ ）
    3. 有两个点属于 $b$ ，且起点就是 $l$ 和 $l + 1$ ，那么 $l + 2$ 一定是由 $l$ 得到的，也可以确定 $x$

然后就可以得到 $x, z$ 了，接着扫描所有点，如果点 $t \in a$ 但 $t - x \notin a$ ，说明它不是由平移得到的点，则 $t \in b$

分析时间，求凸包是 $O(n \log n)$ ，旋转卡壳过程中，每条边只会扫到一次，每个点最多对应到两条边的平行线中，每次我们会把平行线中的点最多扫描 $3$ 次，所以时间是 $O(n \log n + n) = O(n \log n)$ 的，瓶颈在求凸包

代码

有几个要点：

  1. 求凸包的时候排序了，点的顺序已经被打乱
  2. 不开 long long 见祖宗
  3. 发现就算点共线，只要凸包求对了，还是每条边去找最大平行范围判断也可以得到正确答案，但这样时间退化成 $O(n^2)$ ，直接 TLE 所以所有点共线的情况特判只计算一次，是 $O(n)$ 的
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
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb(x) emplace_back(x)
using PLL = std::pair<long long, long long>;
using LL = long long;
const int N = 1e5 + 100;
int n, stk[N], top;
PLL a[N];
bool vis[N];
std::pair<int, PLL> ans;
std::vector<int> b;
std::map<PLL, int> ha;
int ne(int x){ return x + 1 - top + ((x + 1 - top) >> 31 & top); }
PLL operator - (PLL x, PLL y){ return {x.fi - y.fi, x.se - y.se}; }
PLL operator + (PLL x, PLL y){ return {x.fi + y.fi, x.se + y.se}; }
PLL operator * (PLL x, LL y){ return {x.fi * y, x.se * y}; }
LL operator * (PLL x, PLL y){ return x.fi * y.se - x.se * y.fi; }
LL area(PLL x, PLL y, PLL z){ return (y - x) * (z - x); }
void convex(PLL *x, int n)
{
    std::sort(x, x + n);
    top = 0;
    for (int i = 0; i < n; ++i)
    {
        while (top >= 2 && area(x[stk[top - 2]], x[stk[top - 1]], x[i]) < 0) vis[stk[--top]] = false;
        vis[stk[top++] = i] = true;
    }
    vis[0] = false;
    for (int i = n - 1; ~i; --i) if (!vis[i])
    {
        while (top >= 2 && area(x[stk[top - 2]], x[stk[top - 1]], x[i]) < 0) --top;
        stk[top++] = i;
    }
    --top;
}
void upd(int l, int r)
{
    if (l == r) return ;
    if (r == ne(l))
    {
        if (ans.fi < 1) ans = {1, a[stk[r]] - a[stk[l]]};
        return ;
    }
    r = ne(r);
    PLL x = a[stk[l + 1]] - a[stk[l]];
    int st2 = -1, z1 = 0, z2 = 0;
    for (int i = ne(l); i != r; i = ne(i))
        if (a[stk[i]] != a[stk[l]] + x * (z1 + 1))
        {
            st2 = i;
            goto type2;
        }
        else ++z1;
    if (z1 > ans.fi) ans = {z1, x};
    return ;
    type2: z1 = z2 = 0;
    for (int i = ne(l); i != r; i = ne(i)) if (i != st2)
        if (a[stk[i]] == a[stk[l]] + x * (z1 + 1)) ++z1;
        else if (a[stk[i]] == a[stk[st2]] + x * (z2 + 1)) ++z2;
        else goto type3;
    if (z1 != z2) goto type3;
    if (z1 > ans.fi) ans = {z1, x};
    return ;
    type3: x = a[stk[ne(ne(l))]] - a[stk[l]], z1 = z2 = 0;
    for (int i = ne(ne(l)); i != r; i = ne(i))
        if (a[stk[i]] == a[stk[l]] + x * (z1 + 1)) ++z1;
        else if (a[stk[i]] == a[stk[l + 1]] +  x * (z2 + 1)) ++z2;
        else return ;
    if (z1 != z2) return ;
    if (z1 > ans.fi) ans = {z1, x};
}
void rotcal()
{
    for (int i = 1; i < n; ++i)
        if (area(a[0], a[i], a[i - 1]) != 0) goto not_line;
    return upd(0, n - 1);
    not_line:;
    for (int i = 0, j = 1, k = 1; i < top; ++i)
    {
        PLL x = a[stk[i]], y = a[stk[i + 1]];
        j = k;
        while (area(x, y, a[stk[j]]) < area(x, y, a[stk[j + 1]])) j = ne(j);
        k = j;
        while (ne(k) != j && area(x, y, a[stk[k]]) == area(x, y, a[stk[k + 1]])) k = ne(k);
        upd(j, k);
    }
}
void get_b()
{
    if (!ans.fi)
        for (int i = 0; i < n; ++i) b.pb(i + 1);
    else 
        for (int i = 0; i < n; ++i) if (ha.find(a[i] - ans.se) == ha.end()) b.pb(ha[a[i]]);
}
signed main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%lld %lld", &a[i].fi, &a[i].se);
    for (int i = 0; i < n; ++i) ha[a[i]] = i + 1;
    convex(a, n), rotcal(), get_b();
    printf("%ld\n", b.size());
    for (int i : b) printf("%d ", i);
    printf("\n%lld %lld\n%d\n", ans.se.fi, ans.se.se, ans.fi);
    return 0;
}