【计算几何】【前缀和】2019雅礼集训 Convex

题目：

给出一个凸包，在其中选择两个顶点，切割成两个凸多边形，求所有方案的两个凸多边形的面积差之和。

分析：

其实是非常简单的题

首先，绝对值非常麻烦，所以考虑一种不用绝对值的求面积方式：很显然，有向三角形面积法可以表示任意一个凸多边形的面积。并且不需要绝对值。

但是，绝对值没有完全消除，在算面积差时，还是用到了绝对值。因此我们可以限制枚举出来的多边形一定不超过总面积的一半。

这样就有 面积差=总面积-2*较小部分面积。

考虑切割线过每一个点的所有方案。现在需要通过目前这个点的所有方案（所有多边形的面积和），在O(1)以内得到过下一个点的每个多边形对应的面积。

考虑这两组多边形的变化：

显然，每个多边形的变化量是：$?P_A\times P_i+P_A\times P_{i+1}?P_{i+1}\times P_i$

然后，观察差积的表达式：
$X_A?Y_i?Y_A?X_i$
$X_B?Y_i?Y_B?X_i$
$X_C?Y_i?Y_C?X_i$
……
所以，就有：
$(X_A+X_B+X_C+\dots \dots )?Y_i?(Y_A+Y_B+Y_C+\dots \dots )?X_i$

所以，可以通过维护横纵坐标的前缀和，以达到O(1)转移的目的。

#include<cstdio>
#include<cstring>
#include<algorithm>
#define SF scanf
#define PF printf
#define MAXN 4000010
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll,ll> PII;
void Read(ll &x){
    char c;bool flag=0;x=0;while(c=getchar(),c!=EOF&&(c<'0'||c>'9')&&c!='-');if(c=='-') flag=1;else x=c-'0';while(c=getchar(),c!=EOF&&c>='0'&&c<='9') x=x*10ll+c-'0';if(flag) x=-x;
}
int n;
struct Vector{
    ll x,y;Vector() {
    }Vector(ll xx,ll yy):x(xx),y(yy) {
    }Vector operator +(Vector a) const{
    return Vector(x+a.x,y+a.y);}Vector operator -(Vector a) const{
    return Vector(x-a.x,y-a.y);}ll operator ^(Vector a) const{
    return x*a.y-y*a.x;}
}p[MAXN];
ll get_s(Vector x,Vector y,Vector z){
    Vector a=y-x;Vector b=z-x;return abs(a^b);
}
ll get_sum(){
    ll res=0;for(int i=2;i<=n+1;i++)res+=(p[i]^p[i-1]);return res;
}
ll ans;
Vector pre[MAXN];
int main(){
    SF("%d",&n);for(int i=1;i<=2*n;i++){
    if(i<=n)Read(p[i].x),Read(p[i].y);
// SF("%lld%lld",&p[i].x,&p[i].y);elsep[i]=p[i-n];pre[i]=pre[i-1]+p[i];pre[i].x%=MOD;pre[i].y%=MOD;}ll sum=get_sum(),maxs=0,sums=0;int tp=2;for(int i=1;i<=n;i++){
    while((maxs+get_s(p[i],p[tp],p[tp+1]))+(i>(tp-1)%n+1)<=sum/2ll){
    maxs+=get_s(p[i],p[tp],p[tp+1]);tp++;(sums+=maxs)%=MOD;}(ans+=(((tp-i-1)*(sum%MOD)%MOD-2ll*sums)%MOD+MOD)%MOD)%=MOD;sums=((sums-(tp-i-1)*((p[i+1]^p[i])%MOD)%MOD-(p[i]^(pre[tp]-pre[i+1]))%MOD+(p[i+1]^(pre[tp]-pre[i+1]))%MOD)%MOD+MOD)%MOD;maxs-=get_s(p[i],p[i+1],p[tp]);}PF("%lld",ans);
}