「BZOJ2391」Cirno的忧郁

传送门

设p[0] = (-10001,-10001)

把所有点按p[0]极角排序，

s[i][j]表示三角形p[0]p[i]p[j]内的总价值，若i到j极角增大则s为正，否则s为负。

那么答案就是按顺序多边形每条边两个端点的s值之和的绝对值。

如何求s

枚举每个点x，建一颗平衡树，把极角排序在它后面的点一个个加入平衡树，树中的权值为按x极角排序的值。那么加入一个点y时，权值小于y的权值的所有点的和即为s[x][y]。

//Achen

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<vector>

#include<cstdio>

#include<queue>

#include<cmath>

#define eps 1e-15

#define For(i,a,b) for(int i=(a);i<=(b);i++)

#define Rep(i,a,b) for(int i=(a);i>=(b);i--)

const int N=;

typedef long long LL;

typedef double db;

using namespace std;

int n,m,q,qs[N],rak[N];

template<typename T>void read(T &x)  {

    char ch=getchar(); x=; T f=;

    while(ch!='-'&&(ch<''||ch>'')) ch=getchar();

    if(ch=='-') f=-,ch=getchar();

    for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;

}

struct pt {

    LL x,y,w; int id; db slop;

    pt(){}

    pt(LL x,LL y):x(x),y(y){}

}p[N];

pt operator - (const pt&A,const pt&B) { return pt(A.x-B.x,A.y-B.y); }

LL cross(pt A,pt B) { return A.x*B.y-A.y*B.x; }

LL dot(pt A,pt B) { return A.x*B.x+A.y*B.y; }

LL length(pt A) { return dot(A,A); }

int dcmp(db x) { return fabs(x)<=eps?:(x>?:-); }

bool operator <(const pt&A,const pt&B) {

    return dcmp(A.slop-B.slop)>||(dcmp(A.slop-B.slop)==&&length(A-p[])<length(B-p[]));

}

db v[N];

LL w[N],s[N][N],sum[N],rs;

int rt,tot,l[N],r[N],hr[N];

#define lc l[x]

#define rc r[x]

void update(int x) { sum[x]=sum[lc]+sum[rc]+w[x]; }

void left(int &x) {

    int y=r[x];

    r[x]=l[y];

    l[y]=x;

    update(x);

    x=y;

    update(x);

}

void right(int &x) {

    int y=l[x];

    l[x]=r[y];

    r[y]=x;

    update(x);

    x=y;

    update(x);

}

void insert(int &x,db y,LL ww) {

    if(!x) {

        x=++tot;

        hr[x]=rand();

        lc=rc=;

        v[x]=y;

        sum[x]=w[x]=ww;

        rs+=ww;

        return ;

    }

    if(v[x]<y) {

        rs+=sum[lc]+w[x];

        insert(rc,y,ww);

        if(hr[rc]<hr[x]) left(x);

    }

    else {

        insert(lc,y,ww);

        if(hr[lc]<hr[x]) right(x);

    }

    update(x);

}

LL solve(int k) {

    LL res=;

    qs[k+]=qs[];

    For(i,,k)

        res+=s[rak[qs[i]]][rak[qs[i+]]];

    return abs(res);

}

#define DEBUG

int main() {

#ifdef DEBUG

    freopen("2391.in","r",stdin);

    freopen("2391.out","w",stdout);

#endif

    srand();

    read(n); read(m);

    For(i,,n) read(p[i].x),read(p[i].y),p[i].id=i,p[i].w=;

    For(i,,m) read(p[n+i].x),read(p[n+i].y),read(p[n+i].w);

    p[]=pt(-,-);

    For(i,,n+m) p[i].slop=atan2(p[i].y-p[].y,p[i].x-p[].x);

    sort(p+,p+n+m+);

    For(i,,n+m) if(p[i].id) rak[p[i].id]=i;

    For(i,,n+m) {

        rt=; tot=;

        For(j,i,n+m) {

            if(j==) {

                int debug=;

            }

            rs=;

            insert(rt,atan2(p[j].y-p[i].y,p[j].x-p[i].x),p[j].w);

            s[i][j]=rs; s[j][i]=-rs;

        }

    }

    read(q);

    while(q--) {

        int k;

        read(k);

        For(i,,k) read(qs[i]);

        printf("%lld\n",solve(k));

    }

    return ;

}