CF611G New Year and Cake

Link
设(S(l,r))为沿对角线((l,r))分开后对角线左侧的多边形的面积。
对于任意(l)，都存在一个(r)，满足(forall iin[l+2，r],S(l,i)le S(i,l)wedgeforall iin[r+1,l-1],S(i,l)le S(l,i))。
（这里的区间指的是循环下的有向区间）
注意到随着(l)递增，(r)单调不降。
因此我们可以预处理前缀和，然后双指针扫一遍计算答案。
注意long long溢出。

#include<cctype>
#include<cstdio>
using i64=long long;
const int N=500007,P=1000000007;
int read(){int x;scanf("%d",&x);return x;}
struct vec{i64 x,y;}a[N],s[N];
i64 operator*(const vec&a,const vec&b){return a.x*b.y-a.y*b.x;}
vec operator+(const vec&a,const vec&b){return {a.x+b.x,a.y+b.y};}
vec operator-(const vec&a,const vec&b){return {a.x-b.x,a.y-b.y};}
void mod(vec&a){a.x%=P,a.y%=P;}
i64 abs(i64 a){return a<0? -a:a;}
int r[N];i64 t[N];
int main()
{
    int n=read();i64 tmp,tot,ans=0;
    for(int i=1;i<=n;++i) s[i]=s[i-1]+(a[i]={read(),read()}),mod(s[i]);
    for(int i=2;i<=n;++i) tmp=a[i-1]*a[i],r[i]=(r[i-1]+(t[i]=t[i-1]+tmp))%P;
    tot=abs(t[n+1]=t[n]+a[n]*a[1]);
    for(int L=1,R=3;R<=n;++R)
    {
	for(;L<R-1&&tot/2.0<abs(t[R]-t[L]+a[R]*a[L]);++L);
	ans=(ans+t[R]%P*(R-L-1)-r[R-2]+r[L-1]+a[R]*(s[R-2]-s[L-1]))%P;
	ans=(ans+r[L-1]+s[L-1]*a[R]+(t[n+1]-t[R])%P*(L-1))%P;
    }
    printf("%lld",((tot%P*250000002%P*n%P*(n-3)%P+ans)%P+P)*2%P);
}