问题 2603 --Cirno的忧郁

2603: Cirno的忧郁

题目描述

  Cirno 闲着无事的时候喜欢冰冻青蛙。 
雾之湖是一个二维平面。Cirno 每次从雾之湖中固定的 n 个结点中选出一些点构成一个简单多边形, Cirno 运用自己的能力能将此多边形内所有青蛙冰冻。 
雾之湖生活着 m 只青蛙, 青蛙有大有小,所以每只青蛙的价值为一个不大于10000 的正整数。 
Cirno 很想知道每次冻住的青蛙的价值总和。因为智商有限, Cirno 将这个问题交给完美算术教室里的你。 
因为爱护动物, 所以每次冻结的青蛙会被放生。 也就是说一只青蛙可以被多次统计。 

输入

第一行 2 个正整数 n,m。 
以下 n 行,每行 2 个整数 xi,yi, 表示第 i 个结点的坐标。 
再以下 m 行,每行 3 个整数 xj,yj,vj,表示第 j 个青蛙的坐标和价值。 
第 n+m+1 行一个整数 q, 表示有 q 组询问。 
每组询问有 2 行, 第一行一个整数 s(3<=s<=n), 表示简单多边形的结点数。
第二行 s 个正整数,顺时针或逆时针给出多边形的结点的编号(1--n) 

输出

共 q 行。 
对于每个询问, 每行输出一个整数表示冻结的青蛙的价值之和。 

样例输入输出

输入#1 复制
4 3 
2 2 
3 5 
7 4 
5 1 
3 4 2 
4 3 7 
6 3 90 
2 
3 
1 2 3 
4 
1 4 3 2
输出#1 复制
9 
99 

提示

【数据范围】 
对于 30%的数据, n,m<=100; q<=100 
对于 60%的数据, n,m<=100; q<=10000 
对于 100%的数据, n,m<=1000; q<=10000 
-10000<=x,y<=10000; 0<v<=10000 
【注释】 
对于所有 n+m 个结点, 保证不存在三点共线情况。 
样例有三点共线。。。不要在意这些细节

序号 标题 作者 发表时间 费用 订购数 操作