1687.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 37 行

#include"iostream.h"
#include"math.h"
long x[50],y[50];
inline long cheng(int a,int  b,int c)
{return (x[a]-x[b])*(y[a]-y[c])-(x[a]-x[c])*(y[a]-y[b]);}
                   
int main()
{int t,n,m,p[50],h,key,i,j,l;char s[50];long an,anb;
        cin>>t;
        for(;t>0;t--)
        {cin>>n;
                for(i=0;i<n;i++)
                        cin>>x[i]>>y[i];
        cin>>m;key=0;anb=0;
        for(l=0;l<m;l++)
        {cin>>h;
       for(i=0;i<h;i++){cin>>p[i];p[i]--;}
                  
        an=0;
        for(i=1;i<h-1;i++)
                {
                an+=cheng(p[0],p[i],p[i+1]);
                                                }
//      cout<<":::"<<an<<endl;
        if(abs(an)>anb){anb=abs(an);key=l+1; }
        }
                                                                                                                             
cout<<key<<endl;
        }
                
        return 1;
}