随笔-21  评论-10  文章-21  trackbacks-0
    精度卡的很紧,我的精度只能卡到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*+ 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*+ 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 阅读(291) 评论(0)  编辑 收藏 引用 所属分类: geometry

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