 /**//*
题意:给出一个平面图,点有坐标,问给定长度的环的个数,但环内不能有点或边
跟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
搜索
最新评论

|
|