现在的位置: 首页 > 综合 > 正文

2391: Cirno的忧郁

2018年01月13日 ⁄ 综合 ⁄ 共 1972字 ⁄ 字号 评论关闭
//1.AC:return cmul(sub(c,a),sub(b,a));
//	WA:return cmul(sub(b,a),sub(c,a));
//2.AC:sum[k]=sum[ls[k]]+sum[rs[k]]+c[k];
//	WA:sum[k]=sum[ls[k]]+sum[rs[k]];
#include<algorithm>
#include<iostream>
#include<cstdio>
#define N 2005
using namespace std;
struct point{int x,y,id,c;}p[N];
int n,m,x,y,q,root,size,ans,tmp,f[N][N],mark[N],b[N],ls[N],rs[N],rnd[N],num[N],sum[N],c[N];
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
inline int sqr(int x){return x*x;}
inline int dis(point a,point b){return sqr(a.x-b.x)+sqr(a.y-b.y);}
inline point sub(point a,point b){return (point){a.x-b.x,a.y-b.y,0,0};}
inline int cmul(point a,point b){return a.x*b.y-b.x*a.y;}
inline int turn(point a,point b,point c){return cmul(sub(c,a),sub(b,a));}
inline bool cmp(point a,point b){return turn(p[0],a,b)==0?dis(p[0],a)<dis(p[0],b):turn(a,p[0],b)>0;}
void update(int k){sum[k]=sum[ls[k]]+sum[rs[k]]+c[k];}
void lturn(int &k){int t=rs[k];rs[k]=ls[t];ls[t]=k;sum[t]=sum[k];update(k);k=t;}
void rturn(int &k){int t=ls[k];ls[k]=rs[t];rs[t]=k;sum[t]=sum[k];update(k);k=t;}
void insert(int &k,int id){
	if(!k){
		k=++size;
		ls[k]=rs[k]=0;rnd[k]=rand();
		num[k]=id;sum[k]=c[k]=p[id].c;
		return;
	}
	sum[k]+=p[id].c;
	if(turn(p[x],p[num[k]],p[id])>0){
		insert(ls[k],id);
		if(rnd[ls[k]]<rnd[k])rturn(k);
	}
	else{
		insert(rs[k],id);
		tmp+=sum[ls[k]]+c[k];
		if(rnd[rs[k]]<rnd[k])lturn(k);
	}
}
void pre(){
	sort(p+1,p+n+m+1,cmp);
	for(int i=1;i<=n+m;i++)
		mark[p[i].id]=i;
	for(x=1;x<n+m;x++){
		root=size=0;
		for(y=x+1;y<=n+m;y++){
			tmp=0;
			insert(root,y);
			f[x][y]=f[y][x]=tmp;
		}
	}
}
void getans(){ 
	int e=read();
	for(int i=1;i<=e;i++)
		b[i]=mark[read()];
	b[e+1]=b[1];ans=0;
	for(int i=1;i<=e;i++)
		if(turn(p[0],p[b[i]],p[b[i+1]])>0)
			ans+=f[b[i]][b[i+1]];
		else ans-=f[b[i]][b[i+1]];
	if(ans<0)ans=-ans;
	printf("%d\n",ans);
}
int main(){
	n=read();m=read();
	p[0].x=-20000;p[0].y=-20000;
	for(int i=1;i<=n;i++)
		p[i]=(point){read(),read(),i,0};
	for(int i=n+1;i<=n+m;i++)
		p[i]=(point){read(),read(),i,read()};
	pre();
	q=read();
	for(int i=1;i<=q;i++)
		getans();
	return 0;
}

抱歉!评论已关闭.