【Codeforces 611G】New Year and Cake | Mrsrz's blog

计算几何，双指针

题目大意：

给定一个凸 $n$ 边形，它的对角线有 $\frac{n(n-3)}2$ 条。

对每条对角线，会将凸 $n$ 边形分成两部分，这条对角线的贡献为分成的两部分中，面积较大的那部分的面积减去另一部分面积。

求所有的对角线的贡献之和的两倍。

题解：

令凸包面积为 $S$，对每条对角线，其分成的两部分面积设为 $A,S-A$。

令 $S-A\geq A$，则该对角线的贡献为 $S-2A$。

$S$ 是不变的，所以我们只需要求出 所有对角线的 $A$ 的和。

考虑双指针，固定一个端点，并让另一个端点尽可能往后移动。保证这两个点构成的半平面截得的凸包部分的面积始终不超过 $\frac S 2$。

用向量叉积计算面积。

这部分比较好处理，还有就是第一个端点移动时带来的面积变化。

向量叉积满足分配律，所以记一下所有向量的和就可以计算了。

注意诸多爆 long long 的问题。

时间复杂度 $O(n)$。

Code：

#include<iostream>
using namespace std;
typedef long long LL;
typedef unsigned long long uLL;
const int N=5e5+5,md=1e9+7;
struct point{
    LL x,y;
    inline point operator-(const point&rhs)const{return(point){x-rhs.x,y-rhs.y};}
    inline point operator+(const point&rhs)const{return(point){x+rhs.x,y+rhs.y};}
    inline point operator*(const int&a)const{return(point){x*a,y*a};}
}d[N];
uLL S;
int n,ans;
inline LL cross(const point&a,const point&b){return a.x*b.y-a.y*b.x;}
inline int crossMOD(const point&a,const point&b){return(a.x%md*(b.y%md)-a.y%md*(b.x%md)+(LL)md*md)%md;}
inline int NEXT(int x){return x%n+1;}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=n;i;--i)cin>>d[i].x>>d[i].y;
    for(int i=2;i<n;++i)S+=cross(d[i]-d[1],d[i+1]-d[1]);
    ans=S%md*(n*(n-3LL)/2%md)%md;
    d[n+1]=d[1],d[0]=d[n];
    uLL s=0;
    point vec=d[2];
    int ct=1,A=0;
    int cp=0;
    for(int i=1,it=2;i<=n;++i){
        while(s+cross(d[it]-d[i],d[NEXT(it)]-d[i])<=S/2){
            ++ct;
            s+=cross(d[it]-d[i],d[NEXT(it)]-d[i]);
            if(s*2==S)++cp;
            A=(A+s)%md;
            vec=vec+d[NEXT(it)];
            it=NEXT(it);
        }
        ans=(ans-(LL)(2*A%md)+md)%md;
        s-=cross(d[i+1]-d[i],d[it]-d[i]);
        A=(A-crossMOD(d[i+1]-d[i],vec-d[i]*ct)+md)%md;
        --ct;
        vec=vec-d[i+1];
    }
    ans=(ans+cp*(S/2%md))%md;
    cout<<ans<<'\n';
    return 0;
}