【解题报告】zju-1030 Farmland

原题地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=30

题目大意：

平面图有一些点和一条边，要求找这样的多边形：

1.边的数量是k

2.多边形内部没有任何的点和边

3.多边形的每个顶点旁边是两条边，如题目例子中的< v2, v1, v7, v8 , v2, v5, v4, v3 >是不符合题意的，因为v2出现了两次。

求这样的多边形的数量。

题目没有重边和环，且给的图中的边不会相交，整个图是连通的。

  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<cmath>
  4 #define N 205
  5 using namespace std;
  6 class point
  7 {
  8 public:
  9     int x,y;
 10     point(int xx=0,int yy=0){x=xx;y=yy;}
 11     point(point &p){x=p.x;y=p.y;}
 12     point& operator-(const point&);//向量减法
 13     double operator*(const point& p){return x*p.y-y*p.x;}//向量叉乘
 14 };
 15 point& point::operator-(const point& p)
 16 {
 17     point p1(x-p.x , y-p.y);
 18     return p1;
 19 }
 20 double Distance(point& p1,point& p2)
 21 {
 22     return sqrt(pow((p2.y-p1.y),2)+pow((p2.x-p1.x),2));
 23 }
 24 double angle(point& p1,point& p2)//返回值为-3~1
 25 {
 26     if(p2.y>=p1.y) return (p2.x-p1.x)/Distance(p1,p2);
 27     else return -(p2.x-p1.x)/Distance(p1,p2)-2;
 28 }
 29 class G
 30 {
 31 public:
 32     point p[N];
 33     int edg[N][N];
 34     int n;//点的数目
 35     G(int nn);
 36     void psort(int i);
 37     int seach(int vi,int ei,int k);
 38 };
 39 G::G(int nn)
 40 {
 41     int ii,i,iii;
 42     for(ii=0;ii<nn;ii++)
 43     {
 44         cin>>i;
 45         cin>>p[i].x>>p[i].y;
 46         cin>>edg[i][0];
 47         for(iii=1;iii<=edg[i][0];iii++)
 48         {
 49             cin>>edg[i][iii];
 50         }
 51     }
 52     for(ii=1;ii<=nn;ii++)
 53     {
 54         psort(ii);
 55     }
 56 }
 57 void G::psort(int ii)
 58 {
 59     int i,j,t;
 60     for(i=1;i<edg[ii][0];i++)
 61     {
 62         for(j=i+1;j<=edg[ii][0];j++)
 63         {
 64             if(angle(p[ii],p[edg[ii][i]])<angle(p[ii],p[edg[ii][j]]))
 65             {
 66                 t=edg[ii][i];
 67                 edg[ii][i]=edg[ii][j];
 68                 edg[ii][j]=t;
 69             }
 70         }
 71     }
 72 }
 73 int G::seach(int vi,int ei,int k)//从第vi个点的第ei条边开始搜索
 74 {
 75     int a[205],i=0,j,bo=ei;
 76     while(1)
 77     {
 78         a[i++]=vi;
 79         vi=edg[vi][ei];
 80         for(j=1;j<=edg[vi][0];j++)
 81         {
 82             if(edg[vi][j]==a[i-1]) break;
 83         }
 84         if(j!=edg[vi][0]) j++;
 85         else j=1;
 86         ei=j;
 87         if(i>=2&&a[0]==a[i-1]&&a[1]==vi) break;
 88         for(j=1;j<i;j++)
 89         {
 90             if(vi==a[j]) return 0;
 91         }
 92     }
 93     if(i-1==k)
 94     {
 95         int s=0;
 96         for(int j=1;j<=i-1;j++)
 97         {
 98             s+=p[a[j]]*p[a[j-1]];
 99         }
100     if(s>0) return 1;
101     else return 0;
102     }
103     return 0;
104 }
105 int main()
106 {
107     int M,n,k,i,j,t;
108     cin>>M;
109     while(M--)
110     {
111         t=0;
112         cin>>n;
113         G g(n);
114         cin>>k;
115         for(i=1;i<=n;i++)
116         {
117             for(j=1;j<=g.edg[i][0];j++)
118             {
119                 t+=g.seach(i,j,k);
120             }
121         }
122         cout<<t/k<<endl;
123     }
124     return 0;
125 }