/**//* 题意:给出一个平面图,点有坐标,问给定长度的环的个数,但环内不能有点或边 跟zoj 2361类似 每次走时选离当前边最左的(最右也行)走,这样走出的环才最小而且里面没东西 走过的边不用再走,标记为-2 最后遇到环时要判是逆时针的才计数,否则会重复计算 */ #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<vector> using namespace std;
const int MAXN = 218; const double PI = acos(-1.0); const double eps = 1e-15;
vector<pair<double,int> >G[MAXN]; double x[MAXN],y[MAXN]; int N,L,ans; int mark[MAXN][MAXN];
bool ok(double a,double b) { if(b>a+eps)return b+eps<a+PI; return b+eps<a-PI; } void dfs(int u,int v)//edge u->v { if(G[v].size()>1) { vector<pair<double,int> >::iterator it = G[v].begin(); while(it->second!=u)it++; double w = it->first; if(it==G[v].begin())it=--G[v].end(); else it--; if(mark[v][it->second]==-1) { mark[v][it->second]=mark[u][v]+1; dfs(v,it->second); } else if(mark[v][it->second]!=-2&&mark[u][v]-mark[v][it->second]+1==L &&ok(it->first,w))ans++;//逆时针走的才计数 } mark[u][v]=-2;//走过的边要标记为-2 } int main() { int T; for(scanf("%d",&T);T--;) { scanf("%d",&N); for(int i=1;i<=N;i++)G[i].clear(); for(int i=0;i<N;i++) { int u,v,k; scanf("%d",&u); scanf("%lf%lf%d",&x[u],&y[u],&k); while(k--) { scanf("%d",&v); G[u].push_back(make_pair(0.0,v)); } } for(int i=1;i<=N;i++) { for(vector<pair<double,int> >::iterator it=G[i].begin();it!=G[i].end();it++) { it->first = atan2(y[it->second]-y[i],x[it->second]-x[i]);// } sort(G[i].begin(),G[i].end());//按极角排序 } scanf("%d",&L); ans = 0; memset(mark,-1,sizeof(mark));//-1表示还未走,0,1,2..表示长度 for(int i=1;i<=N;i++) for(vector<pair<double,int> >::iterator it=G[i].begin();it!=G[i].end();it++) if(mark[i][it->second]==-1) { mark[i][it->second]=0; dfs(i,it->second); } printf("%d\n",ans); } return 0; }
|
|
常用链接
随笔分类
Links
搜索
最新评论
|
|