题目描述:
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=30
在欧式平面图上找长度为k的简单环, 环中不允许有其他点, 图是联通图.
其中边不能穿过点(题中没说明白, 只说了边不能"cross")
算法分析:
因为是联通图, 我们只需要递归的贪心的去找边就可以了. 枚举一个向量, 然后按照顺(逆)时针的贪心规则去把"区域"找出来.
非法情况有以下几种:
1. unboundry edge , 可能没有其他的联通边.
2. complex circle , 遇到了"反向边", 或者在"封口"的时候, 下一个边不是初始边.
3. 并非inner region, 在递归的过程中不断收集角度, 最后等于多边形内角和才可以哦~
如果不是联通图或者边可以穿过点, 那就爽了...
zoj 1030
#include<iostream>
#include<cstring>
#include<complex>
#include<algorithm>
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
#define debug
typedef complex <double> pnt;
const int N = 205;
const double eps = 1e-8;
const double pi = acos(-1.0);
double tmp[N][N], dis[N][N];
pnt p[N];
vector<int> to[N];
vector<pair<double,int> > G[N];
bool done[N][N], vis[N], visit[N];
int stk[N], tp, n;
inline double fix(double x,double d = 0, double u = 2*pi){
while(x < d) x += 2*pi;
while(x >= u) x -= 2*pi;
return x;
}
int dfs(int u, int f, double angle){
// cout<< u+1 <<" "<<angle<<endl;
if(vis[u]) {
if(stk[0] != u) return -1; // not simple cycle
int v = lower_bound(G[u].begin(), G[u].end(),make_pair(tmp[u][f],f)) - G[u].begin();
v = (v - 1 + G[u].size()) % G[u].size();
v = G[u][v].second;
if(!vis[v]) return -1;
// answer
angle += fix(tmp[u][f] - tmp[u][v]);
// cout<<f+1<<" "<<v+1<<" "<<angle<<endl;
if(abs(angle - (tp-2) * pi) > eps) return -1; // outside region
// cout<<".."<<endl;
return tp;
}
vis[u] = 1;
if(G[u].size() == 1) return -1; // unboundry edge
int v = lower_bound(G[u].begin(), G[u].end(), make_pair(tmp[u][f],f)) - G[u].begin();
v = (v - 1 + G[u].size()) % G[u].size();
v = G[u][v].second;
done[u][v] = 1;
stk[tp++] = u;
return dfs(v,u,angle + fix(tmp[u][f] - tmp[u][v]));
}
int main(){
int cas;
cin >> cas;
while(cas --){
int m, id, v, x, y;
cin >> n;
for(int i = 0; i < n; i++){
cin >> id >> x >> y >> m;
id --;
p[id] = pnt(x,y);
to[id].clear();
for(int j =0; j < m; j++){
cin >> v; v--;
to[id].push_back(v);
}
}
for(int i =0; i < n; i++)
for(int j =0; j < n; j++) if(i != j)
tmp[i][j] =fix( arg(p[j] - p[i]));
for(int i = 0; i < n; i++){
G[i].clear();
for(int j = 0; j < to[i].size(); j++){
G[i].push_back(make_pair(tmp[i][to[i][j]] , to[i][j]));
}
sort(G[i].begin(), G[i].end());
}
int s, ans = 0;
cin >> s;
memset(done, 0, sizeof(done));
for(int i = 0; i < n; i++){
for(int j = 0; j < G[i].size(); j++) {
int v = G[i][j].second;
// cout<<"i j: "<<i+1<<" "<<v+1<<endl;
if(done[i][v]) continue;
memset(vis,0,sizeof(vis));
vis[i] = 1; tp = 1; stk[0] = i;
if( s == dfs(v,i,0))
ans ++;
// cout<<endl;
}
}
cout << ans << endl;
}
}
posted on 2012-09-04 14:39
西月弦 阅读(350)
评论(0) 编辑 收藏 引用 所属分类:
解题报告