 /**//*
題意:給出一個平面圖,點有坐標,問給定長度的環的個數,但環內不能有點或邊
跟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
搜索
最新評論

|
|