Posted on 2010-08-28 23:22
Uriel 閱讀(324)
評論(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;
}