Posted on 2010-08-28 23:22
Uriel 阅读(306)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
计算几何
计算几何大水题，题目求哪个多边形是最外层的，只要算每个多边形的面积，找出最大的一个就行，因为题目给的坐标标号已经是排过序的，所以求面积只要叉积即可~
//Problem: 1687 User: Uriel
//Memory: 388K Time: 0MS
//Language: G++ Result: Accepted
//Computational Geometry -> Cross Product
//2010.08.29
#include<math.h>
#include<stdio.h>
#include<stdlib.h>
struct point
{
int x,y;
}p[55];
int cross_product(point a,point b)
{
return a.x*b.y-a.y*b.x;
}
int main(){
int i,j,cse,n,x,y,tmp,id,pre,sum,maxs,ans;
scanf("%d",&cse);
while(cse--){
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d %d",&p[i].x,&p[i].y);
}
scanf("%d",&x);
maxs=-1;ans=0;
for(i=0;i<x;i++){
scanf("%d",&y);
sum=0;
for(j=0;j<y;j++){
scanf("%d",&id);
id--;
if(j==0){
pre=id;
tmp=id;
}
else{
sum+=cross_product(p[pre],p[id]);
pre=id;
}
}
sum+=cross_product(p[id],p[tmp]);
if(sum>maxs){
maxs=sum;
ans=i+1;
}
}
printf("%d\n",ans);
}
return 0;
}