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, 0, sizeof(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 閱讀(418)
評論(1) 編輯 收藏 引用 所屬分類:
geometry