「CodeForces-1195F」Geometers Anonymous Club(闵可夫斯基和)

发表于 | 分类于 ，

「CodeForces-1195F」Geometers Anonymous Club

给定n个凸包，求第l个到第r个凸包的Minkowski和

题解

求凸包之间的闵可夫斯基和：取出两个凸包的每一条向量，按照极角序排序构成新凸包即可。（相同斜率的向量需要去重）
求多个凸包的闵可夫斯基和的时候可以直接取所有凸包的向量，不同向量的个数就是求和之后凸包的点数。

所以原问题转化为，在第l到r个凸包的向量中，有多少个互不相同的向量。

考虑对向量按凸包从左到右依次编号，标记当前向量上一次出现的位置（如果是第一次出现则pre[i]=0）。离线处理答案，按向量编号从小到大顺序扫描向量集，对向量i上一次出现的位置pre[i]的出现次数计数，用树状数组维护。对于某一个询问Q的L和R，如果存在L<=i<=r且L<=pre[i]<=r，说明该向量在LR区间内重复出现。对于右端点为R的询问LR，它的答案为L到R的凸包的向量总数-LR区间内重复出现的向量个数。

代码

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
#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 3e5 + 10;
 
int x[maxn], y[maxn], tot = 1;
int pre[maxn], pos[maxn], ans[maxn];
vector<pair<int, int> > query[maxn];
int data[maxn];
 
void add(int i, int y) {
    for(i ++; i < maxn; i += i & -i) data[i] += y;
}
 
int sum(int i)
{
    int res = 0;
    for(i ++; i; i -= i & -i) res += data[i];
    return res;
}
 
int main()
{
    int n, k;
    scanf("%d", &n);
    map<pair<int, int> , int> pre_idx;
    for(int i = 0; i < n; i ++)
    {
        pos[i] = tot;
        scanf("%d", &k);
        for(int j = 0; j < k; j ++) scanf("%d%d", &x[j], &y[j]);
        for(int j = 0; j < k; j ++)
        {
            pair<int, int> p(x[(j + 1) % k] - x[j], y[(j + 1) % k] - y[j]);
            int g = __gcd(abs(p.first), abs(p.second));
            p.first /= g, p.second /= g;
            pre[tot] = pre_idx[p];
            pre_idx[p] = tot ++;
        }
    }
    pos[n] = tot ++;
    int q, l, r, x;
    scanf("%d", &q);
    for(int i = 0; i < q; i ++)
    {
        scanf("%d%d", &l, &r);
        ans[i] = pos[r] - pos[-- l];
        query[pos[r]].push_back({pos[l], i});
    }
    for(int i = 0; i < tot; i ++)
    {
        for(auto q : query[i])
        {
            l = q.first, x = q.second;
            ans[x] -= sum(i) - sum(l - 1);
        }
        add(pre[i], 1);
    }
    for(int i = 0; i < q; i ++) printf("%d\n", ans[i]);
    return 0;
}