随笔-21  评论-10  文章-21  trackbacks-0
 1 /*
 2  10:04 - 12:00
 3  自己规定内部始终在左手方向*/
 4 #include<iostream>
 5 #include<cstring>
 6 #include<vector>
 7 #include<cmath>
 8 #include<algorithm>
 9 using namespace std;
10 const int maxn = 1024;
11 
12 int n, ask, pp;
13 int x[maxn], y[maxn];
14 int visit[maxn][maxn];
15 vector<int> next[maxn];
16 
17 double dis(int i, int j){
18     return sqrt( 0.0 + (x[i] - x[j])*(x[i] - x[j]) +(y[i] - y[j])*(y[i] - y[j]) );
19 }
20 
21 bool cmp(const int & i, const int & j){
22     double a = atan2(0.0 + y[i] - y[pp], 0.0 + x[i] - x[pp]) ;
23     double b = atan2(0.0 + y[j] - y[pp], 0.0 + x[j] - x[pp]) ;
24     return a > b || fabs(a - b) < 1e-8 && dis(i, pp) < dis(j, pp);
25 }
26 //再加一个点
27 void input(){
28     scanf("%d",&n); sort(next[pp].begin(), next[pp].end(), cmp);
29     int best = 1;
30     for(int i = 1; i <= n; i++){
31         int id, m;
32         scanf("%d %d %d %d",&id, &x[i], &y[i], &m);
33         next[i].resize(m);
34         for(int j = 0; j < m; j++)scanf("%d",&next[i][j]);
35         if(y[best] > y[i])best = i;
36     }
37     //fill(visit, visit + maxn*maxn, 0);
38     memset(visit, 0sizeof(visit) );
39     x[n+1= x[best];
40     y[n+1= y[best] - 10;
41     next[best].push_back(n+1);
42     next[n+1].push_back(best);
43     n = n + 1;
44     scanf("%d",&ask);
45 }
46 
47 int det(int i, int j, int k){
48     return (x[i] - x[k])*(y[j] - y[k]) -(x[j] - x[k])*(y[i] - y[k]);
49 }
50 
51 void solve(){
52     int ans = 0;
53     for(pp = 1; pp <= n; pp++)
54         sort(next[pp].begin(), next[pp].end(), cmp);
55     for(int i = 1; i <= n; i++)
56         for(int j = 0; j < next[i].size(); j++){
57             int a = i, b = next[i][j];
58             if(visit[a][b])continue;
59             int cnt = 0;
60            // printf("begin(%d->%d): ",a, b);
61             while(!visit[a][b]){
62                 visit[a][b] = (++cnt);
63                 int c;
64                 for(int k = 0; k < next[b].size(); k++)
65                     if(next[b][k] == a){
66                         c = next[b][ (k + 1%  next[b].size() ];
67                         break;
68                     }
69                 if(c==a)break;
70                 a = b, b = c;
71                // printf("(%d->%d): ",a, b);
72             }
73         //  printf("(%d->%d)end\n",a, b);
74           if(visit[a][b] && cnt - visit[a][b] + 1 == ask )ans++;
75     }
76     printf("%d\n",ans);
77 }
78 
79 int main(){
80     //freopen("in","r",stdin);
81     int T;
82     scanf("%d",&T);
83     while(T--){
84         input();
85         solve();
86     }
87 }
88 

posted on 2009-10-20 10:46 wangzhihao 阅读(360) 评论(1)  编辑 收藏 引用 所属分类: geometry

评论:
# re: pku 1092 farmland 2011-06-27 19:44 | Somebody
这个程序有bug吧~

9
1 0 0 2 2 3
2 2 0 2 5 1
3 0 3 2 1 4
4 2 3 2 3 5
5 2 2 6 6 7 8 9 4 2
6 1 2 2 5 7
7 1 1 2 5 6
8 3 2 2 5 9
9 3 1 2 8 5
8
这个数据 应该是输出0的吧
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理