模拟赛 - NOI 模拟五&六

2016.01.02 19:33 Sat| 26 visits oi_2016| 2016_竞赛日常| Text

BZOJ4260 Codechef REBXOR

我猜这是一道 Trie 树的傻题。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 400005

int n, a[N], sum[N], l[N], r[N];

struct node
{
    node *son[2];
    node() { memset(son, 0, sizeof son); }
    void *operator new(size_t s);
} *np, p[13000000];

void *node::operator new(size_t s) { return np++; }

node *root;

void insert(node *&pos, int x, int d)
{
    if (d == -1) return;
    if (!pos->son[(x >> d) & 1])
        pos->son[(x >> d) & 1] = new node();    
    insert(pos->son[(x >> d) & 1], x, d - 1);
}

int query(node *pos, int x, int d)
{
    if (d == -1) return 0;
    if (!pos->son[!((x >> d) & 1)])
        return query(pos->son[(x >> d) & 1], x, d - 1);
    return (1 << d) + query(pos->son[!((x >> d) & 1)], x, d - 1);
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        a[i] = read();
    for (int i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] xor a[i];
    np = p; root = new node();
    for (int i = 1; i <= n; ++i)
        insert(root, sum[i - 1], 30),
        l[i] = max(l[i - 1], query(root, sum[i], 30));
    for (int i = n; i >= 1; --i)
        sum[i] = sum[i + 1] xor a[i];
    np = p; root = new node();
    for (int i = n; i >= 1; --i)
        insert(root, sum[i + 1], 30),
        r[i] = max(r[i + 1], query(root, sum[i], 30));
    long long ans = 0;
    for (int i = 1; i < n; ++i)
        ans = max(ans, 0ll + l[i] + r[i + 1]);
    cout << ans << endl;
    return 0;
}

Escape

问题描述

有一天,n 维空间中某空间站的守卫遭到外星舰队袭击,经过鏖战,守卫已经打光了所有弹药。外星人很快攻入了空间站,守卫连忙派人与外星人谈判,原来,他们是冲着空间站的宝钻来的。守卫赶紧拿着宝钻乘飞船逃离。

守卫的飞船比外星舰队快(所以牺牲了战斗力,难怪打不赢)。但守卫们发现守卫的飞船动力系统损伤严重,所以跑得还没外星人快了。

在这个情况下,守卫们拿出了它们的法宝:超级运输机。整个空间可看成一个 维坐标系,空间站是坐标系中的一个点。这个运输机有一个操控盘,上有 n 列,每列 m 行,第 i 行的第 j 列有两个正整数参数 aij、bij,表示可以使守卫的飞船的第 j 维坐标增加 aij ,但是同时有个副作用就是会把外星人的飞船的第 j 维坐标增加 bij。每一列有一个手柄,移动到哪一个位置就表示这一维的移动方式是哪一种。

但是这个运输机有一个严重的缺陷,不能有两个手柄移动到同一行。

显然,守卫逃离得离外星人越远越好,但是为了减少空间站的人的担忧,它们希望空间站的人也认为它们离外星人比较远,空间站的人只能知道它们与外星人离空间站的距离,所以守卫们想在最大化离外星人的距离的前提下,最大化守卫与外星人距离空间站的距离的商。

输入

输入文件名为(escape.in)。

第一行两个整数n,m。

接下来一个 m * n 的矩阵,表示 aij

接下来一个 m * n 的矩阵,表示 bij

输出

输出文件名为(escape.out)。

输出一行两个数,分别为最大化的距离和最大化距离的前提下最大化的商。精确到 3 位小数即视为正确。

样例输入

3 3
2 3 2
3 2 3
2 3 2
1 4 3
4 1 2
3 2 1

样例输出

1.732051 2.000000

数据范围与约定

对于30%的数据:n,m <= 8。

对于70%的数据:n,m <= 100。

对于100%的数据:n <= 100, m <= 5000,所有数均不大于104

题解

第一问显然可以用费用流跑出来。第二问是在第一问取最大值的基础上进行的询问,所以可以将第一问作为第一关键字,01 分数规划作为第二关键字去跑费用流。

这样直接来的话,第 4~7 个测试点会被卡常数,后三个测试点会跑 88s。

如果我们用迭代法求 01 分数规划的话,会快大约 10 倍。

考虑优化边数。对于每一个维度,显然最好都去选能跑得最远的方式,除非两个维度撞车,这时有一个维度才需要做出让步。发现每一个维度可能去选择的方式最多只有 n 种,因此可以在连边时优化,使得边数减少到 n*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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <bits/stdc++.h>
using namespace std;

#define N 6005
#define inf 0x7fffffff
#define sqr(x) ((x) * (x))

int n, m, s, t, cnt, head[N], a[5005][105], b[5005][105];
pair<int, double> tdis[N], dis[105];
int inc[N], from[N]; pair<double, double> d[N];
bool v[N];

pair<double, double> operator +(pair<double, double> a, pair<double, double> b)
{ return make_pair(a.first + b.first, a.second + b.second); }
pair<double, double> operator *(pair<double, double> &a, double b)
{ return make_pair(a.first * b, a.second * b); }
pair<double, double> operator -(pair<double, double> &a)
{ return make_pair(-a.first, -a.second); }

struct graph
{
    int next, to, val; pair<double, double> cost;
    graph() {}
    graph(int _next, int _to, int _val, pair<double, double> _cost)
    : next(_next), to(_to), val(_val), cost(_cost) {}
} edge[50000];

inline void add(int x, int y, int z, pair<double, double> w)
{
    edge[++cnt] = graph(head[x], y, z, w);
    head[x] = cnt;
    edge[++cnt] = graph(head[y], x, 0, -w);
    head[y] = cnt;
}

queue<int> q;

bool spfa()
{
    memset(v, 0, sizeof(v));
    for (int i = 0; i <= n + m + 1; ++i)
        d[i] = make_pair(1e99, 1e99);
    d[s] = make_pair(0, 0); v[s] = 1; inc[s] = inf;
    q.push(s);
    while (!q.empty())
    {
        int x = q.front(), y; q.pop(), v[x] = 0;
        for (int i = head[x]; i; i = edge[i].next)
            if (edge[i].val && d[y = edge[i].to] > d[x] + edge[i].cost)
            {
                d[y] = d[x] + edge[i].cost;
                inc[y] = min(inc[x], edge[i].val); from[y] = i;
                if (!v[y]) v[y] = 1, q.push(y);
            }
    }
    return d[t] != make_pair(1e99, 1e99);
}

pair<double, double> update()
{
    int x = t;
    while (x != s)
    {
        edge[from[x]].val -= inc[t];
        edge[from[x] ^ 1].val += inc[t];
        x = edge[from[x] ^ 1].to;
    }
    return d[t] * inc[t];
}

pair<double, double> edmonds_karp()
{
    pair<double, double> re;
    while (spfa())
        re = re + update();
    return re;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    freopen("escape.in", "r", stdin);
    freopen("escape.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            a[i][j] = read();
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            b[i][j] = read();
    s = 0; t = m + n + 1;
    pair<double, double> temp;
    double ans = 50, last;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            tdis[j] = make_pair(abs(a[j][i] - b[j][i]), 1.0 * a[j][i] / b[j][i]);
        nth_element(tdis + 1, tdis + m - n + 1, tdis + m + 1);
        dis[i] = tdis[m - n + 1];
    }
    do
    {
        last = ans;
        memset(head, 0, sizeof head); cnt = 1;
        for (int i = 1; i <= m; ++i)
            add(0, i, 1, make_pair(0, 0));
        for (int i = 1; i <= n; ++i)
            add(m + i, m + n + 1, 1, make_pair(0, 0));
        for (int j = 1; j <= n; ++j)
            for (int i = 1; i <= m; ++i)
                if (make_pair(abs(a[i][j] - b[i][j]), 1.0 * a[i][j] / b[i][j]) >= dis[j])
                    add(i, m + j, 1, make_pair(-sqr(a[i][j] - b[i][j]), -sqr(a[i][j]) + ans * sqr(b[i][j])));
        temp = edmonds_karp();
        double t1 = 0, t2 = 0;
        for (int i = m + 1; i <= m + n; ++i)
            for (int j = head[i]; j; j = edge[j].next)
                if (edge[j].val && edge[j].to != t)
                    t1 += sqr(a[edge[j].to][i - m]), t2 += sqr(b[edge[j].to][i - m]);
        ans = t1 / t2;
    } while (fabs(last - ans) > 4e-4);
    cout << fixed << setprecision(10);
    cout << sqrt(-temp.first) << ' ' << sqrt(ans) << endl;
    return 0;
}

往事 Recollection

问题描述

往事太多,有时候忘了就忘了吧。

如果有非记不可的,就只能用点附加手段啦!

我们定义一棵往事树是一个n个点n-1条边的有向无环图,点编号为1到n,其中1号点被称为是根结点,除根结点以外,每个点都恰有一条出边(即以其作为起点的边)。每条边上有1个字符(这里我们实际上用一个不大于300的非负整数代表不同的字符),对于任意一个点u,u的所有入边(即以其为终点的边)上的字符互不相同。

接下来我们定义往事,点u对应的往事为u到根的路径(显然有且只有一条)上的所有边按照从u到根经过的顺序排序后边上的字符依次拼接形成的字符串,简记为r(u)。

一棵往事树的联系度取决于它包含的所有往事之中最相近的一对的相似度。具体的,我们定义2个点u和点v对应的往事的相似度f(u,v)如下。

f(u,v)=Lcp(r(u),r(v))+Lcs(r(u),r(v))

其中Lcp(a,b)表示字符串a和b的最长公共前缀的长度,Lcs(a,b)表示字符串a和b的最长公共后缀的长度。

定义一棵往事树的联系度为所有满足1<=u<v<=n的f(u,v)的最大值。

现在,给出一棵往事树,请你给出这棵往事树的联系度。

输入

输入文件名为(recollection.in)。

第一行一个大于1的整数n表示给定的往事树的结点数。

接下来n-1行,每行2个整数。其中第i(1<=i<n)行的2个数依次表示点i+1的出边的终点和边上的字符。

输出

输出文件名为(recollection.out)。

一行一个整数表示这棵往事树的联系度。

样例输入

7
1 1
1 2
2 1
2 2
5 1
5 2

样例输出

3

数据范围与约定

对于前10%的数据,n<=200。

对于前30%的数据,n<=1500。

另外有20%的数据,存在且仅存在一条边,使得其他所有边上的字符均相同。

对于全部数据,n<=200000,出于简化目的,保证每条边的起点编号大于终点。

原题解

对 trie 建出后缀数组,枚举 LCA,用线段树维护每个点子树内所有串在后缀数组中的顺序以更新答案。

从叶子往上线段树合并维护即可。

题解

我并不会对 trie 建后缀数组,所以 hash 之后 sort 就好了……时间复杂度 O(n*log2n)。

我懒得写线段树的合并,所以写了 set 的启发式合并。

注意 hash 的时候,要使用正确的姿势。

注意启发式合并时,可以边插入边查询和旁边的元素的 lcs。如果每一层暴力推上去,再扫一遍更新答案,就会发生恐怖的事情。

// 我最开始这哈希都写的什么玩意啊,只错了一个点。

 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
#include <bits/stdc++.h>
using namespace std;

#define N 200005

int n, deep[N], fa[N][18], sa[N], rnk[N], minh[N][18], base[N];
long long power[N], h[N][18];
set<int> s[N];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

inline bool cmp(int x, int y)
{
    for (int i = 17; i >= 0; --i)
        if (h[x][i] == h[y][i])
            x = fa[x][i], y = fa[y][i];
    return h[x][0] < h[y][0];
}

int dist(int x, int y)
{
    int tx = x, ty = y;
    for (int i = 17; i >= 0; --i)
        if ((1 << i) < min(deep[tx], deep[ty]) && h[tx][i] == h[ty][i])
            tx = fa[tx][i], ty = fa[ty][i];
    return deep[x] - deep[tx];
}

inline int getmin(int x, int y)
{
    int t = base[y - x + 1];
    return min(minh[x][t], minh[y - (1 << t) + 1][t]);
}

inline int getlcs(set<int> &s, int x)
{
    static set<int>::iterator t1, t2;
    t1 = t2 = s.insert(x).first;
    if (s.size() == 1) return -0x3f3f3f3f;
    if (t1 == s.begin()) return getmin(x + 1, *++t2);
    if (++t2 == s.end()) return getmin(*--t1 + 1, x);
    return min(getmin(*--t1 + 1, x), getmin(x + 1, *t2));
}

int main()
{
    freopen("recollection.in", "r", stdin);
    freopen("recollection.out", "w", stdout);
    cin >> n;
    deep[1] = 1;
    for (int i = 2; i <= n; ++i)
        fa[i][0] = read(), deep[i] = deep[fa[i][0]] + 1, h[i][0] = read() + 1;
    power[0] = 1;
    for (int j = 1; j <= n; ++j)
        power[j] = power[j - 1] * 13131;
    for (int j = 1; j <= 17; ++j)
        for (int i = 1; i <= n; ++i)
            fa[i][j] = fa[fa[i][j - 1]][j - 1],
            h[i][j] = h[fa[i][j - 1]][j - 1] * power[1 << j] + h[i][j - 1];
    for (int i = 1; i <= n; ++i)
        sa[i] = i;
    sort(sa + 1, sa + n + 1, cmp);
    for (int i = 1; i <= n; ++i)
        rnk[sa[i]] = i;
    for (int i = 2; i <= n; ++i)
        minh[i][0] = dist(sa[i - 1], sa[i]);
    for (int i = 2; i <= n; ++i)
        base[i] = base[i >> 1] + 1;
    for (int j = 1; j <= 17; ++j)
        for (int i = 1; i + (1 << j) - 1 <= n; ++i)
            minh[i][j] = min(minh[i][j - 1], minh[i + (1 << (j - 1))][j - 1]);
    int ans = 0;
    for (int i = n; i; --i)
    {
        ans = max(ans, deep[i] - 1 + getlcs(s[i], rnk[i]));
        if (s[fa[i][0]].size() < s[i].size()) swap(s[fa[i][0]], s[i]);
        for (set<int>::iterator j = s[i].begin(); j != s[i].end(); ++j)
            ans = max(ans, deep[fa[i][0]] - 1 + getlcs(s[fa[i][0]], *j));
    }
    cout << ans << endl;
    return 0;
}

Which dreamed it

问题描述

有n个房间,每个房间有若干把钥匙能够打开特定房间的门。

你会做这么件事情:

最初你在房间1。

每当你到达一个房间,你可以选择该房间的一把钥匙,前往该钥匙对应的房间,并将该钥匙丢到垃圾桶中。

你希望:最终回到房间1,且垃圾桶中有所有的钥匙。

求方案数。两组方案不同,当且仅当使用钥匙的顺序不同。注意,每把钥匙都是不同的。

输入

输入文件名为(w.in)。

有多组数据。

对于每组数据第一行输入一个数n,表示房间数。

接下来n行一次描述每个房间:

首先一个数s,表示这个房间的钥匙数目,接下来s个数,分别描述每把钥匙能够打开的房间的门。

输入以n=0结尾。

输出

输出文件名为(w.out)。

对于每组数据,输出方案数,为了方便你的输出,请将答案对1000003取模。

样例输入

1
0
2
1 1
2 1 2
0

样例输出

1
0

样例解释

在第一组样例中,没有钥匙,则方案数为1。

在第二组样例中,你不能使用第二个房间的钥匙,所以方案数为0。

数据范围与约定

对于30%的数据:房间数和钥匙数都小于等于20。

对于另20%的数据:房间数小于等于5,钥匙数大概比较小。

对于100%的数据:房间数小于等于100,钥匙数小于等于200000。

数据数组也不是特别多。

题解

这题,一眼以蔽之,つまらない。考这题还不如告诉大家:有一个很有趣的结论,可以数欧拉路径的条数。

平衡有向图中从某一条边出发的欧拉路径的条数等于关于起始点的树形图个数与每一个结点出度的阶乘之积。其中前一部分可以用矩阵树定理求解,以 i 点为根的树形图个数等于关联矩阵的 aii 代数余子式的值。由于求出的是从某一条边出发的条数,所以答案还要乘上根节点的出度。

 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
#include <bits/stdc++.h>
using namespace std;

#define mod 1000003

long long power(long long a, int b)
{
    long long re = 1;
    while (b)
    {
        if (b & 1) re = re * a % mod;
        a = a * a % mod; b >>= 1;
    }
    return re;
}

long long fac[200005], mat[105][105];
int n, in[105], out[105];

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    freopen("w.in", "r", stdin);
    freopen("w.out", "w", stdout);
    fac[0] = 1;
    for (int i = 1; i <= 200000; ++i)
        fac[i] = fac[i - 1] * i % mod;
    while (cin >> n, n)
    {
        memset(mat, 0, sizeof mat);
        memset(in, 0, sizeof in);
        memset(out, 0, sizeof out);
        for (int i = 1; i <= n; ++i)
        {
            out[i] = read();
            for (int x, j = 1; j <= out[i]; ++j)
                x = read(), --mat[i][x], ++in[x];
        }
        long long ans = out[1];
        for (int i = 1; i <= n; ++i)
            if (in[i] != out[i]) { puts("0"); goto end; }
        for (int i = 1; i <= n; ++i)
            mat[i][i] += in[i];
        for (int i = 2; i <= n; ++i)
        {
            int t = 0;
            for (int j = i; j <= n; ++j)
                if (mat[j][i]) { t = j; break; }
            if (t == 0) { puts("0"); goto end; }
            else if (i != t)
            {
                ans = -ans;
                for (int j = 2; j <= n; ++j)
                    swap(mat[i][j], mat[t][j]);
            }
            long long rev = power(mat[i][i], mod - 2);
            for (int j = i + 1; j <= n; ++j)
                if (mat[j][i])
                {
                    int t = mat[j][i] * rev % mod;
                    for (int k = i; k <= n; ++k)
                        mat[j][k] = (mat[j][k] - mat[i][k] * t) % mod;
                }
        }
        for (int i = 2; i <= n; ++i)
            ans = ans * mat[i][i] % mod;
        ans = (ans % mod + mod) % mod;
        for (int i = 1; i <= n; ++i)
            ans = ans * fac[out[i] - 1] % mod;
        cout << ans << endl;
        end :;
    }
    return 0;
}

游戏

问题描述

主人公是 Alice&Bob。

游戏规则:

初始有 N 堆石子,第 i 堆中有 a[i]个石子。

Alice 和 Bob 轮流操作, 每次操作, 操作的一方选择两个整数 A, B,满足 1<=A<=当前的堆数, B*2<=当前第 A 堆中石子数量。 设当前第 A 堆石子中有 C个石子, 从第 A 堆中取走 2*B 个石子,将这些石子扔掉扔掉,并加入一堆新的石子,这堆新的中有 C-B 个石子。 无法操作者输。

Alice 先手,问如果两人都执行最优策略,谁会赢。

输入

输入文件名为(game.in)。

多组测试,第一行一个整数 T 表示组数。

对于每组数据,第一行一个整数 N。

第二行 N 个整数,表示 a[]。

输出

输出文件名为(game.out)。

对于每组数据,输出赢家。

样例输入

2
2
4 3
1
2

样例输出

Bob
Alice

数据范围与约定

对于10%的数据:N = 1。

对于50%的数据:a[] <= 100。

对于100%的数据:N <= 1000,1 <= a[] <= 109, T <= 100。

题解

随便找找规律就好了的样子。

 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
#include <bits/stdc++.h>
using namespace std;

int a[] = {1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, 31, 32, 35,
            37, 38, 41, 42, 44, 47, 49, 50, 52, 55, 56, 59, 61, 62, 64, 67, 69,
            70, 73, 74, 76, 79, 81, 82, 84, 87, 88, 91, 93, 94, 97, 98, 100};
int t, n;

int sg(int x)
{
    int temp = 0;
    while (++x)
    {
        if (x == 0 || x == 1) return 0;
        if (x % 3 == 0) return a[temp];
        x = x / 3, ++temp;
    }
    return 0;
}

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int main()
{
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
    cin >> t;
    while (t--)
    {
        cin >> n;
        int ans = 0;
        while (n--) ans ^= sg(read());
        puts(ans ? "Alice" : "Bob");
    }
    return 0;
}

阴影面积

阴影面积等于所有点在给定平面上的凸包的面积。我们可以转一转,将给定的三角形转到 x, y 平面上,之后投影什么的就很方便了。

对于那个三角形 ABC,先将 A 点平移到原点,再绕着 x 轴转直到 B 点落到 x, y 平面上,之后绕着 z 轴转使得 B 点与 x 轴重合。最后绕着 x 轴转使 C 点也落到 x, y 平面上,变换就完成了。求变换角度,直接用 atan2 就可以。

  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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
using namespace std;

#define sqr(x) ((x) * (x))
#define dcmp(x) ((x) < 1e-8)
#define pi 3.1415926535

struct point3
{
    double x, y, z;
    point3(double _x = 0.0, double _y = 0.0, double _z = 0.0)
    : x(_x), y(_y), z(_z) {}
    point3 operator +(point3 p) { return point3(x + p.x, y + p.y, z + p.z); }
    point3 operator -(point3 p) { return point3(x - p.x, y - p.y, z - p.z); }
    point3 operator *(double d) { return point3(x * d, y * d, z * d); }
    friend istream &operator >>(istream &in, point3 &p)
    { in >> p.x >> p.y >> p.z; return in; }
    friend ostream &operator <<(ostream &out, point3 p)
    { out << '(' << p.x << ", " << p.y << ", " << p.z << ')'; return out; }
};

struct point
{
    double x, y;
    point(double _x = 0.0, double _y = 0.0) : x(_x), y(_y) {}
    bool operator <(const point &p) const
    { return x == p.x ? y < p.y : x < p.x; }
    point operator +(point p) { return point(x + p.x, y + p.y); }
    point operator -(point p) { return point(x - p.x, y - p.y); }
    point operator *(double d) { return point(x * d, y * d); }
    friend double dot(point a, point b) { return a.x * b.x + a.y * b.y; }
    friend double cross(point a, point b) { return a.x * b.y - a.y * b.x; }
    friend point rotate(point p, double a)
    { return point(p.x * cos(a) - p.y * sin(a), p.x * sin(a) + p.y * cos(a)); }
    friend double dist(point a, point b)
    { return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y)); }
    friend istream &operator >>(istream &in, point &p)
    { in >> p.x >> p.y; return in; }
    friend ostream &operator <<(ostream &out, point p)
    { out << '(' << p.x << ", " << p.y << ')'; return out; }
};

inline bool check(vector<point> &s, point &p)
{
    point temp = s.back(); s.pop_back();
    if (cross(temp - s.back(), p - temp) < 1e-6)
        return false;
    s.push_back(temp); return true;
}

double convex_hull(int n, point p[])
{
    vector<point> q;
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; ++i)
    {
        while ((int)q.size() > 1 && !check(q, p[i]));
        q.push_back(p[i]);
    }
    int temp = q.size();
    for (int i = n - 1; i >= 1; --i)
    {
        while ((int)q.size() > temp && !check(q, p[i]));
        q.push_back(p[i]);
    }
    double re = 0;
    for (int i = 1; i < (int)q.size(); ++i)
        re += cross(q[i - 1], q[i]);
    return re / 2;
}

point3 a, b, c, s, cp[105];
point np[105];
int n;

point3 rotate(bool flag, point3 p, double a)
{
    if (flag == false)
    {
        point t = rotate(point(p.y, p.z), a);
        return point3(p.x, t.x, t.y);
    }
    else
    {
        point t = rotate(point(p.x, p.y), a);
        return point3(t.x, t.y, p.z);
    }
}

void rotate(bool flag, point3 p)
{
    if (flag == false)
    {
        if (p.z == 0) return;
        double t = atan2(p.z, p.y);
        b = rotate(false, b, -t);
        c = rotate(false, c, -t);
        s = rotate(false, s, -t);
        for (int i = 1; i <= n; ++i)
            cp[i] = rotate(false, cp[i], -t);
    }
    else
    {
        if (p.y == 0) return;
        double t = atan2(p.y, p.x);
        b = rotate(true, b, -t);
        c = rotate(true, c, -t);
        s = rotate(true, s, -t);
        for (int i = 1; i <= n; ++i)
            cp[i] = rotate(true, cp[i], -t);
    }
}

int main()
{
    freopen("shadow.in", "r", stdin);
    freopen("shadow.out", "w", stdout);
    cin >> a >> b >> c >> s;
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> cp[i];
    b = b - a, c = c - a, s = s - a;
    for (int i = 1; i <= n; ++i)
        cp[i] = cp[i] - a;
    rotate(false, b);
    rotate(true, b);
    rotate(false, c);
    for (int i = 1; i <= n; ++i)
    {
        double cx = s.x + (cp[i].x - s.x) / (s.z - cp[i].z) * s.z,
               cy = s.y + (cp[i].y - s.y) / (s.z - cp[i].z) * s.z;
        np[i] = point(cx, cy);
    }
    cout << fixed << setprecision(2) << fabs(convex_hull(n, np)) << endl;
    return 0;
}