本文主要是介绍【HDU 5448】Marisa’s Cake，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给你一个包含n个点的凸包，所有可能出现凸包的面积和。
分析：首先比较暴力的方法就是n^2枚举一条边，求它对答案的贡献。但是点的个数有10^5，因此我们考虑从某一个点出发的所有有向面积。
若我们当前考虑的是第i个点，那么它与第i+1个点形成的这条边所能产生的凸包个数为(2^(n - 2) - 1)个，与第i + 2个点形成的这条边的个数为(2 ^ (n - 3) - 1)个……又因为叉积满足分配律，因此可以先搞出来一个前缀和。而当在考虑第i + 1个点时，只需要把第i + 1个点的贡献减掉，然后再把除了第i个点的贡献乘2+1即可。复杂度为on
code：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const LL mod = 1e9 + 7;
const LL Inv = (mod + 1) / 2;
const int N = 100005;
struct Node{LL x,y;Node(){}Node(LL x,LL y):x(x),y(y){}Node operator - (const Node &a)const{return Node((x - a.x + mod) % mod,(y - a.y + mod) % mod);}Node operator + (const Node &a)const{return Node((x + a.x) % mod,(y + a.y) % mod);}Node operator * (const LL &b){return Node(x * b % mod,y * b % mod);}LL operator ^ (const Node &a)const{return (x * a.y - y * a.x) % mod;}void add(){scanf("%lld%lld",&x,&y);}
};
Node nd[N];
LL Pow[N];
void solve(){int n;scanf("%d",&n);for(int i = 0 ; i < n ; i ++) nd[i].add();Node tmp(0,0),sum(0,0);LL res = 0;for(int i = 1 ; i < n ; i ++){tmp = tmp + nd[i] * (Pow[n - i - 1] - 1);if(i != 1) sum = sum + nd[i];}for(int i = 0 ; i < n ; i ++){res += nd[i] ^ tmp;res %= mod;tmp = tmp - nd[i + 1] * (Pow[n - 2] - 1);tmp = tmp * 2;tmp = tmp + sum;sum = sum - nd[(i + 2) % n] + nd[i];}res = (res + mod) % mod;printf("%lld\n",abs(res));
}
int main(){Pow[0] = 1;for(int i = 1 ; i < N ; i ++)Pow[i] = Pow[i - 1] * 2 % mod;int _;scanf("%d",&_);while(_--) solve();return 0;
}这篇关于【HDU 5448】Marisa’s Cake的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
