原题地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=30
题目大意：
平面图有一些点和一条边，要求找这样的多边形：
1.边的数量是k
2.多边形内部没有任何的点和边
3.多边形的每个顶点旁边是两条边，如题目例子中的< v2, v1, v7, v8 , v2, v5, v4, v3 >是不符合题意的，因为v2出现了两次。
求这样的多边形的数量。
题目没有重边和环，且给的图中的边不会相交，整个图是连通的。
#include<stdio.h>
#include<iostream>
#include<cmath>
#define N 205
using namespace std;
class point
{
public:
int x,y;
point(int xx=,int yy=){x=xx;y=yy;}
point(point &p){x=p.x;y=p.y;}
point& operator-(const point&);//向量减法
double operator*(const point& p){return x*p.y-y*p.x;}//向量叉乘
};
point& point::operator-(const point& p)
{
point p1(x-p.x , y-p.y);
return p1;
}
double Distance(point& p1,point& p2)
{
return sqrt(pow((p2.y-p1.y),)+pow((p2.x-p1.x),));
}
double angle(point& p1,point& p2)//返回值为-3~1
{
if(p2.y>=p1.y) return (p2.x-p1.x)/Distance(p1,p2);
else return -(p2.x-p1.x)/Distance(p1,p2)-;
}
class G
{
public:
point p[N];
int edg[N][N];
int n;//点的数目
G(int nn);
void psort(int i);
int seach(int vi,int ei,int k);
};
G::G(int nn)
{
int ii,i,iii;
for(ii=;ii<nn;ii++)
{
cin>>i;
cin>>p[i].x>>p[i].y;
cin>>edg[i][];
for(iii=;iii<=edg[i][];iii++)
{
cin>>edg[i][iii];
}
}
for(ii=;ii<=nn;ii++)
{
psort(ii);
}
}
void G::psort(int ii)
{
int i,j,t;
for(i=;i<edg[ii][];i++)
{
for(j=i+;j<=edg[ii][];j++)
{
if(angle(p[ii],p[edg[ii][i]])<angle(p[ii],p[edg[ii][j]]))
{
t=edg[ii][i];
edg[ii][i]=edg[ii][j];
edg[ii][j]=t;
}
}
}
}
int G::seach(int vi,int ei,int k)//从第vi个点的第ei条边开始搜索
{
int a[],i=,j,bo=ei;
while()
{
a[i++]=vi;
vi=edg[vi][ei];
for(j=;j<=edg[vi][];j++)
{
if(edg[vi][j]==a[i-]) break;
}
if(j!=edg[vi][]) j++;
else j=;
ei=j;
if(i>=&&a[]==a[i-]&&a[]==vi) break;
for(j=;j<i;j++)
{
if(vi==a[j]) return ;
}
}
if(i-==k)
{
int s=;
for(int j=;j<=i-;j++)
{
s+=p[a[j]]*p[a[j-]];
}
if(s>) return ;
else return ;
}
return ;
}
int main()
{
int M,n,k,i,j,t;
cin>>M;
while(M--)
{
t=;
cin>>n;
G g(n);
cin>>k;
for(i=;i<=n;i++)
{
for(j=;j<=g.edg[i][];j++)
{
t+=g.seach(i,j,k);
}
}
cout<<t/k<<endl;
}
return ;
}