精度卡的很緊,我的精度只能卡到1e－6，開到1e－7都要掛，真是很險很險的過了....
基本做法就是對每個未知數去試探性的解，能解就解，不能解就放那，單獨處理多解的情況，最后判三角形是否合法。不過這樣寫也寫了很長。
1 #include<iostream>
2 #include<cstdio>
3 #include<cmath>
4 using namespace std;
5
6 const double eps = 1e-6;
7 const double PI = 3.1415926535897932384626;
8
9
10 int dcmp(double x){
11 return x < -eps ? -1 : x > eps;
12 }
13 struct triangle{
14 double bian[3];
15 double jiao[3];
16 void in(){
17 scanf("%lf %lf %lf %lf %lf %lf",&bian[0], &jiao[0] ,&bian[1], &jiao[1], &bian[2], &jiao[2]);
18 }
19 bool check(){
20 for(int i = 0; i < 3; i++){
21 if(dcmp(bian[i])<=0)return false;
22 if(dcmp(jiao[i])<=0 || dcmp(jiao[i])>=PI)return false;
23 }
24 if( dcmp(jiao[0] + jiao[1] + jiao[2] - PI)!=0)return false;
25 double judge = bian[0] / sin (jiao[0]);
26 for(int i = 1; i < 3; i++){
27 if(dcmp( judge - bian[i] / sin (jiao[i]) ) != 0)return false;
28 }
29 return true;
30 }
31 };
32
33 triangle ans;
34
35 bool crack1(double a, double b, double theta, double & c){
36 if( dcmp(c+1)!=0 || dcmp(a)<=0 || dcmp(b)<=0 || dcmp(theta)<=0 || dcmp(theta) >= PI)return false;
37 c = a*a + b*b - 2*a*b*cos(theta);
38 if(dcmp(c)<=0){
39 c = -1;
40 return false;
41 }
42 c = sqrt(c);
43 return true;
44 }
45
46 bool crack2(double a, double alpha, double beta, double & b){
47 if(dcmp(b+1)!=0 || dcmp(a) <= 0 || dcmp(alpha)<= 0 || dcmp(alpha)>= PI || dcmp(beta)<=0 || dcmp(beta)>= PI)return false;
48 b = a / sin(alpha) * sin(beta);
49 return true;
50 }
51
52 bool crack3(double a, double b, double c, double & theta){
53 if(dcmp(theta+1) != 0 || dcmp(a)<=0 || dcmp(b)<=0 || dcmp(c)<=0)return false;
54 theta = ( a*a + b*b - c*c ) / (2*a*b);
55 if( dcmp(theta+1) < 0 || dcmp(theta-1) > 0 ){
56 theta = -1;
57 return false;
58 }
59 if( dcmp(theta+1) == 0 )theta = -1;
60 if( dcmp(theta-1) == 0 )theta = 1;
61 theta = acos(theta);
62 return true;
63 }
64
65 bool crack4(double alpha, double beta, double & gamma){
66 if( dcmp(gamma+1)!=0 || dcmp(alpha)<= 0 || dcmp(alpha)>= PI || dcmp(beta)<= 0 || dcmp(beta)>= PI)return false;
67 gamma = PI - alpha - beta;
68 if(dcmp(gamma)<= 0 || dcmp(gamma)>= PI ){
69 gamma = -1;
70 return false;
71 }
72 return true;
73 }
74
75 void dfs(){
76 for(int i = 0; i < 3; i++)
77 {
78 if( crack4( ans.jiao[(i+1)%3], ans.jiao[(i+2)%3], ans.jiao[i]) )dfs();
79 if( crack2(ans.bian[(i+1)%3], ans.jiao[(i+1)%3], ans.jiao[i], ans.bian[i]) )dfs();
80 if( crack2(ans.bian[(i+2)%3], ans.jiao[(i+2)%3], ans.jiao[i], ans.bian[i]) )dfs();
81 if( crack1(ans.bian[(i+1)%3], ans.bian[(i+2)%3], ans.jiao[i], ans.bian[i]) )dfs();
82 if( crack3(ans.bian[(i+1)%3], ans.bian[(i+2)%3], ans.bian[i], ans.jiao[i]) )dfs();
83 }
84 }
85
86
87 bool last_crack(){
88 int cnt1 = 0, cnt2 = 0, id1, id2;
89 for(int i = 0; i < 3; i++){
90 if( dcmp(ans.bian[i]+1) != 0 ){
91 cnt1++; if(dcmp(ans.jiao[i]+1) != 0 )id2 = i; else id1 = i;
92 }
93 if( dcmp(ans.jiao[i]+1) != 0 )cnt2++;
94 }
95 if(!(cnt1==2 && cnt2==1) )return false;
96 if(dcmp(ans.bian[id1])<=0 || dcmp(ans.bian[id2])<=0
97 || dcmp(ans.jiao[id2])<=0 || dcmp(ans.jiao[id2])>= PI)return false;
98
99 if( dcmp( ans.bian[id1] - ans.bian[id2]) >= 0 )return true;
100 ans.jiao[id1] = asin( ans.bian[id1] / (ans.bian[id2] / sin(ans.jiao[id2]) ) );
101 dfs();
102 return false;
103 }
104
105
106 int main(){
107 int t;
108 for(scanf("%d",&t); t > 0; t--){
109 ans.in();
110 dfs();
111 if(last_crack())
112 printf("More than one solution.\n");
113 else{
114 if( ans.check() ){
115 for(int i = 0; i < 2; i++)
116 printf("%.10lf %.10lf ",ans.bian[i], ans.jiao[i]);
117 printf("%.10lf %.10lf\n",ans.bian[2], ans.jiao[2]);
118 }else
119 printf("Invalid input.\n");
120 }
121 }
122 }
posted on 2009-10-31 21:38
wangzhihao 閱讀(353)
評論(0) 編輯 收藏 引用 所屬分類:
geometry