#include#include #include #include using namespace std;const double eps = 1e-6;const int inf = 0x3f3f3f3f;int n,m;int f[100];struct point{ double x,y; point(double xx = 0,double yy = 0){ this->x = xx; this->y = yy; } void read(){ scanf("%lf%lf",&x,&y); }}p[100];struct Q{ int l,r,c;}q[1005];bool judge(point pp,point p1,point p2){///向量叉积。推断顺逆时针时注意三个点的先后位置 /// <0是就是第一个向量在第二个向量的逆时针方向； return ((p1.x-pp.x)*(p2.y-pp.y)-(p2.x-pp.x)*(p1.y - pp.y)) < -eps;}Q tra(point t,int c){ Q ans; bool flag[100]; memset(flag,false,sizeof(flag)); for(int i = 0; i < n; i++){ if(judge(t,p[i],p[i+1])){///推断能不能照到这条边 ///（实际上推断转化成了照到点）； flag[i] = true; } } ///以下是处理得出的数据，保存下每一个灯所能照到的最左端和最右端； if(flag[n-1]&&flag[0]){ int left = n-1; while(flag[left-1]){left--;} int right = 0; while(flag[right+1]){right++;} ans.l = left; ans.r = right + n; } else{ int left = 0,right = n-1; while(!flag[left]){left++;} while(!flag[right]){right--;} ans.l = left; ans.r = right; } ans.c = c; return ans;}bool solve(){ int ans = inf; for(int i = 0; i < n; i++){ memset(f,inf,sizeof(f)); f[i] = 0; for(int j = 0; j < n; j++){ int r = i + j;///从第i个点開始往后数了j个； ///多定义这么一个层次，能够使状态的转移变得有序 for(int k = 0; k < m; k++){ if(q[k].l > r) continue;///当前点与该灯照亮的最左点之间有空隔，就不符合開始更新的条件； if(q[k].r < r) continue;///这是个剪枝，去掉也对；就是不再考虑不会成为最优解的情况； int now = min(q[k].r + 1, i + n);///依据区间右端点往后更新。可是一旦更新过了i+n就要将端点定为i+n； f[now] = min(f[now],f[r] + q[k].c); } } ans = min(ans,f[i+n]); } if(ans == inf) return false; printf("%d\n",ans); return true;}int main(){ while(scanf("%d",&n) != EOF){ if(n == 0) break; for(int i = 0; i < n; i++){ p[i].read(); } p[n] = p[0]; scanf("%d",&m); point temp;int c; for(int i = 0; i < m; i++){ temp.read(); scanf("%d",&c); q[i] = tra(temp,c); } if(!solve()) printf("Impossible.\n"); } return 0;}