1
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77#include<iostream> #include<string.h> #include<stdlib.h> #include<stdio.h> #include<algorithm> #include<string> #include<map> #include<math.h> using namespace std; struct node { int x,y; }; node a[10]; int s[10],c[10]; int n; bool check1(double mid) { double k=a[c[1]].x; for(int i=2;i<=n;i++) { k=k+mid; if(k>a[c[i]].y) return false; if(k<a[c[i]].x) k=a[c[i]].x; } return true; } bool check(double mid) { for(int i=1;i<=n;i++) c[i]=i; for(int i=1;i<=s[n];i++) { if(check1(mid)) return true; next_permutation(c+1,c+n+1); } return false; } int main() { int cnt=0; s[1]=1; for(int i=2;i<=10;i++) s[i]=s[i-1]*i; while(scanf("%d",&n),n!=0) { for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].y); double l=0,r=1500; while(l+1e-5<r) { double mid=(l+r)/2; if(check(mid)) l=mid; else r=mid; } int s=(int)l,t=(int)((l-s)*60+0.5); if(t==60) { t=0; s++; } printf("Case %d: %d:",++cnt,s); if(t<10) printf("0%dn",t); else printf("%dn",t); } return 0; }
2
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205#include<iostream> #include<string> #include<string.h> #include<stdlib.h> using namespace std; struct dat_edge { int aim,last; }edge[201]; int n,m,k,inde[101],coun[101],tmp_coun[101],pl[101],len_edge,num_key,key[300][101]; char kind[101]; void insert_edge(int x,int y) { len_edge++; edge[len_edge].aim=y; edge[len_edge].last=pl[x]; pl[x]=len_edge; } void init(int o,string z) { int p,i,num; string t; p=1; z+=' '; for(i=1;i<z.length();i++) if(z[i]==' ') { t=z.substr(p,i-p); if(t[0]=='i') num=0; else num=n; if(t.length()==2) num+=t[1]-'0'; else { num+=(t[1]-'0')*10+t[2]-'0'; } coun[o]++; insert_edge(num,o); p=i+1; } } bool solve(int key[],int poi,int sta) { int i,p,o,w,tmp,que[101],f[101]; for(i=1;i<=n+m+k;i++) { f[i]=0; } for(i=1;i<=n;i++) f[i]=key[i]; for(i=1;i<=m;i++) { if(kind[i]=='a') f[i+n]=1; else f[i+n]=0; } o=n;w=0; for(i=1;i<=n;i++) que[i]=i; while(w<o) { w++; if(que[w]==poi) { if(sta==2) f[que[w]]=!f[que[w]]; else f[que[w]]=sta; } p=pl[que[w]]; while(p!=-1) { coun[edge[p].aim]--; if(coun[edge[p].aim]==0) { que[++o]=edge[p].aim; } tmp=edge[p].aim; if(kind[tmp-n]=='a') { if(f[que[w]]==0) f[tmp]=0; } else if(kind[tmp-n]=='o') { if(f[que[w]]==1) f[tmp]=1; } else if(kind[tmp-n]=='x') { f[tmp]=f[tmp]^f[que[w]]; } else { f[tmp]=!f[que[w]]; } p=edge[p].last; } } for(i=1;i<=n+m+k;i++) coun[i]=tmp_coun[i]; for(i=1;i<=k;i++) { if(f[inde[i]+n]!=key[n+i]) return false; } return true; } void work(int t) { int i,j,p,ans1,ans2,coun_ans; bool ok=true; for(i=1;i<=num_key;i++) { if(!solve(key[i],-1,-1)) { ok=false; break; } } if(ok) { cout<<"Case "<<t<<": No faults detectedn"; return; } ans1=ans2=coun_ans=0; for(i=1;i<=m;i++) { for(j=0;j<=2;j++) { ok=true; for(p=1;p<=num_key;p++) { ok=solve(key[p],i+n,j); if(!ok) break; } if(ok) { ans1=i; ans2=j; coun_ans++; } } } if(coun_ans!=1) { cout<<"Case "<<t<<": Unable to totally classify the failuren"; return; } if(ans2==2) { cout<<"Case "<<t<<": Gate "<<ans1<<" is failing; output invertedn"; return; } if(ans2==0) { cout<<"Case "<<t<<": Gate "<<ans1<<" is failing; output stuck at 0n"; return; } if(ans2==1) { cout<<"Case "<<t<<": Gate "<<ans1<<" is failing; output stuck at 1n"; return; } } int main() { int t,i,j; string z; t=0; while(cin>>n>>m>>k && n+m+k!=0) { t++; memset(coun,0,sizeof(coun)); len_edge=-1; for(i=1;i<=n+m+k;i++) pl[i]=-1; for(i=1;i<=m;i++) { cin>>kind[i]; getline(cin,z); init(i+n,z); } for(i=1;i<=n+m+k;i++) tmp_coun[i]=coun[i]; for(i=1;i<=k;i++) cin>>inde[i]; cin>>num_key; for(i=1;i<=num_key;i++) for(j=1;j<=n+k;j++) cin>>key[i][j]; work(t); } return 0; }
3
复制代码
1#include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>#include<math.h>using namespace std;#define FOR(I,A,B) for(I=int(A);I<int(B);++I)#define MEM(A,B) memset(A,B,sizeof(A));#define CPY(A,B) memcpy(A,B,sizeof(B));const double pi=acos(-1.0);struct TPoint{ double x,y,z; void get(double a,double b,double c) { x=a;y=b;z=c; }};TPoint p[5];TPoint A,B;int a1,a2,a3,a4,ca;double l;void init(){ l=5*sqrt(2.); p[0].get(0,0,l); p[1].get(l,0,0); p[2].get(0,l,0); p[3].get(-l,0,0); p[4].get(0,-l,0);}double eps(double x){ return x<1e-6&&x>-1e-6;}void getpoint(double a1,double a2,TPoint &A){ double l2,r,aa=(int)a1%90; a1=a1/180*pi; a2=a2/180*pi; aa=aa/180*pi; l2=l/(sin(aa)+cos(aa)); r=l2*l/(l*sin(a2) + l2*cos(a2)); A.x=r*sin(a2)*cos(a1); A.y=r*sin(a2)*sin(a1); A.z=r*cos(a2);}double sqr(double x){ return x*x;}double dis(TPoint a,TPoint b){ return sqrt(sqr(a.x-b.x) + sqr(a.y-b.y) + sqr(a.z-b.z));}int pre(int x){ return (x+3)%4;}int nxt(int x){ return (x+1)%4;}TPoint point(double ra,int x,int y){ TPoint ret; ret.x=(p[x].x-p[y].x)*ra + p[y].x; ret.y=(p[x].y-p[y].y)*ra + p[y].y; ret.z=(p[x].z-p[y].z)*ra + p[y].z; return ret;}double getang(double a,double b,double c){ if(eps(c)||eps(a-b-c)) return 0; return acos((sqr(a)+sqr(b)-sqr(c))/(2*a*b));}double cal(int p1,int p2,TPoint A,TPoint B){ TPoint C,D; double L,R,mid1,mid2,ret(1e10); if(a4>90) { int i; a4=180-a4; FOR(i,0,4) { L=0;R=1; while(R-L>1e-4) { mid1=L+(R-L)/3; C=point(mid1,i+1,nxt(i)+1); mid2=R-(R-L)/3; D=point(mid2,i+1,nxt(i)+1); if(cal(p1,i,A,C)+cal(i,p2,C,B)>cal(p1,i,A,D)+cal(i,p2,D,B)) L=mid1; else R=mid2; } ret=min(ret,cal(p1,i,A,C)+cal(i,p2,C,B)); } return ret; } if(p1==p2) return dis(A,B); if(nxt(p2)==p1) { swap(p1,p2); swap(A,B); } if(nxt(p1)==p2) { double an,a=dis(A,p[0]),b=dis(B,p[0]); an=getang(10,a,dis(A,p[nxt(p1)+1]))+getang(10,b,dis(B,p[nxt(p1)+1])); return sqrt(sqr(a)+sqr(b)-2*a*b*cos(an)); } int i; L=0;R=1; while(R-L>1e-4) { mid1=L+(R-L)/3; C=point(mid1,0,p1+1); mid2=R-(R-L)/3; D=point(mid2,0,p1+1); if(dis(A,C)+cal(pre(p1),p2,C,B)>cal(pre(p1),p2,D,B)+dis(A,D)) L=mid1; else R=mid2; } ret=cal(pre(p1),p2,C,B)+dis(A,C); L=0;R=1; while(R-L>1e-4) { mid1=L+(R-L)/3; C=point(mid1,0,nxt(p1)+1); mid2=R-(R-L)/3; D=point(mid2,0,nxt(p1)+1); if(cal(nxt(p1),p2,C,B)+dis(A,C)>cal(nxt(p1),p2,D,B)+dis(A,D)) L=mid1; else R=mid2; } ret=min(ret,cal(nxt(p1),p2,C,B)+dis(A,C)); return ret;}int main(){ init(); while(scanf("%d%d%d%d",&a1,&a2,&a3,&a4),a1+a2+a3+a4!=-4) { if(a2>90&&a4>90) a2=180-a2,a4=180-a4; if(a2>a4) { swap(a1,a3); swap(a2,a4); } getpoint(a1,a2,A); if(a4>90) getpoint(a3,180-a4,B); else getpoint(a3,a4,B); printf("Case %d: %.3lfn",++ca,cal(a1/90,a3/90,A,B)); } return 0;}
复制代码
1
最后
以上就是坚强芒果最近收集整理的关于2009 ACM-ICPC世界总决赛试题分析1-3的全部内容，更多相关2009内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复