题解 P7429 [THUPC2017] 气氛
清烛
·
·
题解
在博客里面访问（连接较不稳定）
或者 CSDN
Before we start
前置知识：
没了。
Description
## Solution
首先，这 $n + 1$ 个点肯定是参与构成了整个凸包的，因为点的坐标一定为 $0$ 或 $1$。
而我们想想 $n -1$ 维空间中 $n$ 个点构成的凸包的体积，无非就是用这 $n$ 个点张成 $n - 1$ 个向量，然后求出行列式的值除以 $n$ 的阶乘取绝对值，证明可以随便搜一下或者直接当结论记住。也可以手推一下 $2$ 维和 $3$ 维空间的情况发现其是对的。
可是我们这题的点有 $n + 1$ 个，没办法直接用行列式做，怎么办呢？
不妨从二维的情况考虑起。
考虑求四边形 $ABCD$ 的体积，不难发现我们可以依次求 $\triangle ABC$，$\triangle BCD$，$\triangle ABD$ 和 $\triangle ACD$ 的面积，在图上已经显示出来。然后会发现这样刚好将每个区域覆盖了两次。
考虑三维的情况。
然后考虑 $\binom 5 4 = 5$ 个四面体，发现他们的体积加起来也就是整个凸包的体积的两倍。
所以我们可以大胆猜想，**$n - 1$ 维空间中 $n + 1$ 个点构成的凸包的体积等于所有选 $n$ 个点构成的凸包体积之和的一半。**
事实上这也是正确的，~~我太屑了不会证明~~。
于是这道题就做完了。具体地，每次选择一个不出现的点，然后随便取一个点为起点算出 $n - 1$ 个向量，然后高斯消元计算出这 $n - 1$ 个向量组成的 $n - 1$ 维行列式（消成对角阵之后直接将对角线元素相乘），把这些行列式的值加起来。得到的结果除以二输出即可。
## Implement
实现的时候需要注意：
- 题目要求我们乘上 $(n - 1)!$ 后输出，所以我们不用除以 $(n - 1)!$ 了。
- 由于我们需要**行列式的值的绝对值**，所以不能进行模意义下的高斯消元，需要使用 double 进行高斯消元。
- 消元完后得到的行列式的值需要四舍五入成 `long long`（可能爆 `int`）然后计入答案。
- 最后乘上 $2$ 的逆元 $5\times10^8 + 4$。
```cpp
#include <cstdio>
#include <cctype>
#include <cmath>
#include <algorithm>
#define il inline
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define DEC(i, a, b) for (int i = (a); i >= (b); --i)
namespace fastIO {}
using namespace fastIO;
const int maxn = 40, mod = 1e9 + 7, inv2 = 5e8 + 4;
struct Point {//存储点/向量
int dim;
int x[maxn];
} p[maxn];
Point operator-(const Point &a, const Point &b) {
Point ret;
ret.dim = a.dim;
FOR(i, 1, ret.dim) ret.x[i] = a.x[i] - b.x[i];
return ret;
}
typedef double db;
db mat[maxn][maxn];
int n;
double det(int n, db a[40][40]) {//Gauss-Jornan 消元计算行列式
FOR(i, 1, n) {
int r = i;
FOR(j, i + 1, n)
if (fabs(a[j][i]) > fabs(a[r][i])) r = j;
std::swap(a[r], a[i]);
FOR(k, 1, n) {
if (k == i) continue;
db div = a[k][i] / a[i][i];
FOR(j, i + 1, n) a[k][j] -= div * a[i][j];
}
}
db ret = 1;
FOR(i, 1, n) ret *= a[i][i];
return ret;
}
int main() {
int t;
read(t);
while (t--) {
read(n);
FOR(i, 1, n + 1) {
p[i].dim = n - 1;
FOR(j, 1, n - 1) read(p[i].x[j]);
}
int ans = 0;
FOR(ban, 1, n + 1) {//枚举不使用的点
int st = (ban == 1) ? 2 : 1;//随便定起点
for (int j = 1, col = 1; j <= n + 1 && col <= n - 1; ++j, ++col) {
while (j == st || j == ban) ++j;
Point tmp = p[j] - p[st];
FOR(r, 1, n - 1) mat[r][col] = tmp.x[r];//算出向量然后加进矩阵里面
}
ans = (ans + (long long)fabs(round(det(n - 1, mat)))) % mod;//这里要开 long long
}
print(1ll * ans * inv2 % mod), putchar('\n');
}
return output(), 0;
}
```