hdu 5448 Marisa’s Cake（几何+凸包）

本文主要是介绍hdu 5448 Marisa’s Cake（几何+凸包），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：hdu 5448 Marisa’s Cake

解题思路

这题和zoj 3871 Convex Hull有点像，不过点数比较大，不能接受$o(n^2)$的算法。但是题目给定的是一个凸包，所以可以通过化简，在$o(n)$的复杂度内计算出答案。

首先，对于一个三角形ABC

$$S_{ABC} = f_A \times f_B + f_B \times f_C + f_C \times f_A (f_i 表示点i和原点组成的向量）$$
那么对于i和j两点，只需要计算 $f_i \times f_j$和 $f_j \times f_i$对ans的贡献值是多少即可。

$$ans = \sum_{i=1}^{n} \sum_{j=1}^{i-1} ((2^{i-j-1}-1) \times f_i \times f_j + (2^{n-i+j-1}-1) \times f_j \times f_i)$$
$$ans = \sum_{i=1}^{n} \sum_{j=1}^{i-1} (2^{i-j-1}\times f_i \times f_j - f_i \times f_j+ 2^{n-i+j-1} \times f_j \times f_i - f_j \times f_i)$$
$$ans = \sum_{i=1}^{n} \sum_{j=1}^{i-1} (2^{i-j-1}\times f_i \times f_j + 2^{n-i+j-1} \times f_j \times f_i)$$
$$ans = \sum_{i=1}^{n} (2^{i-1}f_i \times \sum_{j=1}^{i-1}(2^{-j}f_j) + \sum_{j=1}^{i-1}(2^{j}f_j) \times 2^{n-i-1}f_i)$$
在过程中维护 $\sum_{j=1}^{i-1}(2^{-j}f_j)$和 $\sum_{j=1}^{i-1}(2^{j}f_j)$

代码

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
typedef long long ll;
const int maxn = 100005;
const int mod = 1e9 + 7;struct Point {int x, y;Point(int x = 0, int y = 0): x(x), y(y) {}void read () { scanf("%d%d", &x, &y); }int operator * (const Point& u) { return (1LL * x * u.y % mod - 1LL * y * u.x % mod + mod) % mod; }Point operator * (const int u) { return Point(1LL * u * x % mod, 1LL * u * y % mod); }Point operator + (const Point& u) { return Point((x+u.x)%mod, (y+u.y)%mod); }
};int N, mul[maxn], inv[maxn];int mul_mod(ll x, int n, int mod) {int ret = 1;while (n) {if (n&1) ret = x * ret % mod;x = x * x % mod;n >>= 1;}return ret;
}int main () {mul[0] = inv[0] = 1;for (int i = 1; i < maxn; i++) mul[i] = 2 * mul[i-1] % mod;ll inv2 = mul_mod(2, mod-2, mod);for (int i = 1; i < maxn; i++) inv[i] = inv2 * inv[i-1] % mod;int cas;scanf("%d", &cas);while (cas--) {int ans = 0;scanf("%d", &N);Point fi, fg, fh;for (int i = 1; i <= N; i++) {fi.read();ans = (ans + 1LL * mul[i-1] * (fi * fh) % mod) % mod;ans = (ans + 1LL * (i==N?inv2:mul[N-i-1]) * (fg * fi) % mod) % mod;fg = fg + fi * mul[i];fh = fh + fi * inv[i];}printf("%d\n", ans);}return 0;
}

这篇关于hdu 5448 Marisa’s Cake（几何+凸包）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---