原题地址: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 ;
}

最新文章

  1. 李洪强经典iOS面试题11
  2. hyperVisor
  3. 【模拟】Codeforces 711A Bus to Udayland
  4. MySQL删除重复记录的方法
  5. 创建自己的github代码库
  6. iOS开发——闪光灯
  7. Hibernate双向关联的增删改操作的属性
  8. php获取二维数组中某一列的值集合
  9. Keras Model Sequential模型接口
  10. JAVA日常之二
  11. 如果debug调试的时候中断总是停在析构函数的delete[] p上
  12. XmlHelpers
  13. Modbus库开发笔记之一:实现功能的基本设计(转)
  14. [原][osg][osgearth]倾斜摄影2.文件格式分析:OSGB
  15. 查看Linux系统版本信息(转)
  16. 2018.10.30 bzoj4942: [Noi2017]整数(线段树压位)
  17. nmap 中的idle scan
  18. JS进阶系列之作用域链
  19. Java String 中的一些函数与正则的结合使用
  20. VFL使用

热门文章

  1. struts.properties的参数描述
  2. Linux网络编程5&mdash;&mdash;使用UDP协议实现群聊
  3. UVA 10497 - Sweet Child Makes Trouble 高精度DP
  4. Spring框架学习之第8节
  5. UITableview刷新某一个cell或section
  6. Java-马士兵设计模式学习笔记-观察者模式-OOD 封装Listener
  7. iOS:地图:MapKit和CoreLocation
  8. Eclipse中使用正则表达式搜索替换
  9. Hadoop、Pig、Hive、Storm、NOSQL 学习资源收集
  10. testNG中@Factory详解