OJ Board

Code: Select all

 /*Parts removed*/

//returns true if a is strictly less than b
bool lesser(long double a,long double b);

//returns true if a is less than or equal to b
bool lessequal(long double a,long double b);

//returns true if the input number is -1
bool used(long double d);

//returns true if a is equal to b, with precision .000 000 01
bool close(long double a,long double b);

//returns true if there's something wrong with the angles
bool anglesum(long double& alpha,long double& beta,long double& gamma){
  int u=0;
  if(used(alpha)) u++;
  if(used(beta)) u++;
  if(used(gamma)) u++;
  if(u<2) return false;
  if(u==3) return !close(alpha+beta+gamma,pi);
  if(!used(alpha)){
    if(lessequal(pi,beta+gamma)) return true;
    alpha=pi-beta-gamma;
  }
  if(!used(beta)){
    if(lessequal(pi,alpha+gamma)) return true;
    beta=pi-alpha-gamma;
  }
  if(!used(gamma)){
    if(lessequal(pi,alpha+beta)) return true;
    gamma=pi-beta-alpha;
  }
  return false;
}

//returns true if there's something wrong with the sides
bool sidesum(long double& a,long double& b,long double& c){
  int u=0;
  if(used(a)) u++;
  if(used(b)) u++;
  if(used(c)) u++;
  if(u<3) return false;
  if(lessequal(a+b,c)) return true;
  if(lessequal(c+b,a)) return true;
  if(lessequal(a+c,b)) return true;
  return false;
}

//called only if you know three sides of a triangle
//returns true if there's a contradiction
//otherwise sets all the angles
bool sss(long double& a,long double& alpha,long double& b,long double& beta,long double& c,long double& gamma){
  long double nalpha=acos((a*a-b*b-c*c)/(-2*b*c));
  if(used(alpha) && !close(alpha,nalpha))
    return true;
  alpha=nalpha;
  long double nbeta=acos((b*b-a*a-c*c)/(-2*a*c));
  if(used(beta) && !close(beta,nbeta))
    return true;
  beta=nbeta;
  long double ngamma=acos((c*c-a*a-b*b)/(-2*a*b));
  if(used(gamma) && !close(gamma,ngamma))
    return true;
  gamma=ngamma;
  return false;
}

//called only if you know two sides and the angle between
//returns true if there's a contradiction
//otherwise sets all the other fields
bool sas(long double& c,long double& alpha,long double& b,long double& gamma,long double& a,long double& beta);

//called only if you know two angles(and therefore the third) and a side
//returns true if there's a contradiction
//otherwise sets all the other fields
bool asa(long double& gamma,long double& a,long double& beta,long double& c,long double& alpha,long double& b);

//called only if you know two sides and an angle not between them
//returns 0 if there's a contradiction
//returns 1 if there are two triangles
//otherwise sets all the other fields and returns 6
int ssa(long double& a,long double& b,long double& alpha,long double& beta,long double& c,long double& gamma);

//returns an empty vector on invalid inputs
//returns a singleton on multiple solutions
//returns all the data if it can be found
vector<long double> solve(vector<long double> v){
  vector<long double> bad;

  // if any of the sides or angles are out of range, invalid input
  for(int i=0;i<v.size();i+=2)
    if(side(v[i]))
      return bad;
  for(int i=1;i<v.size();i+=2)
    if(angle(v[i]))
      return bad;

  if(anglesum(v[1],v[3],v[5])) return bad;
  if(sidesum(v[0],v[2],v[4])) return bad;

  //side side side
  if(used(v[0]) && used(v[2]) && used(v[4])){
    if(sss(v[0],v[1],v[2],v[3],v[4],v[5]))
      return bad;
    return v;
  }

  //the fields of the triangle, clockwise (0=a, 1=alpha,2=b,3=beta,4=c,5=gamma)
  int pn[]={0,3,4,1,2,5};

  //side angle side
  for(int k=0;k<6;k+=2){
    if(used(v[pn[k%6]]) && used(v[pn[(1+k)%6]]) && used(v[pn[(2+k)%6]])){
      if(sas(v[pn[k%6]],v[pn[(k+1)%6]],v[pn[(k+2)%6]],v[pn[(k+3)%6]],v[pn[(k+4)%6]],v[pn[(k+5)%6]]))
        return bad;
      return v;
    }
  }

  //angle side angle
  for(int k=1;k<6;k+=2){
    if(used(v[pn[k%6]]) && used(v[pn[(1+k)%6]]) && used(v[pn[(2+k)%6]])){
      if(asa(v[pn[k%6]],v[pn[(k+1)%6]],v[pn[(k+2)%6]],v[pn[(k+3)%6]],v[pn[(k+4)%6]],v[pn[(k+5)%6]]))
        return bad;
      return v;
    }
  }

  //side side angle
  
  //look at 3 possibilities
  for(int k=0;k<6;k+=2){
    if(used(v[pn[k%6]]) && used(v[pn[(4+k)%6]]) && used(v[pn[(3+k)%6]])){
      int t=ssa(v[pn[k%6]],v[pn[(k+4)%6]],v[pn[(k+3)%6]],v[pn[(k+1)%6]],v[pn[(k+2)%6]],v[pn[(k+5)%6]]);
      if(t==0) return bad;
      if(t==1) return vector<long double>(1);
      return v;
    }
  }

  //take the reflection and look at the other 3
  for(int k=0;k<6;k+=2){
    if(used(v[pn[k%6]]) && used(v[pn[(2+k)%6]]) && used(v[pn[(3+k)%6]])){
      int t=ssa(v[pn[k%6]],v[pn[(k+2)%6]],v[pn[(k+3)%6]],v[pn[(k+5)%6]],v[pn[(k+4)%6]],v[pn[(k+1)%6]]);
      if(t==0) return bad;
      if(t==1) return vector<long double>(1);
      return v;
    }
  }

  return bad;
}

Code: Select all

6
10.00000000 0.50000000 20.00000000 -1.00000000 -1.00000000 -1.00000000
10.00000000 0.50000000 -1.00000000 -1.00000000 20.00000000 -1.00000000
20.00000000 -1.00000000 10.00000000 0.50000000 -1.00000000 -1.00000000
-1.00000000 -1.00000000 10.00000000 0.50000000 20.00000000 -1.00000000
20.00000000 -1.00000000 -1.00000000 -1.00000000 10.00000000 0.50000000
-1.00000000 -1.00000000 20.00000000 -1.00000000 10.00000000 0.50000000

Code: Select all

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

struct set{
       double a;
       double l;
       };


void sss(struct set *p);
void set_two_side(struct set *p);
double countangle(struct set *s);
double cosvalue(struct set *s,int n);
int test(struct set *s,int rl,int ra);
int ssa(struct set *p,int side,int angle);
int compare(const void *f1,const void *f2);
double value(struct set *p,double area,double n);
void set_two_angle_by_sinvalue(struct set *s,int n);

int main()
{
    int n,i;
    struct set tri[3];
    //record known angle and len
    int rl,ra,temp,y,judge;
    int valid;
    scanf("%d",&n);
    for(n;n>0;n--){
        for(i=0,ra=0,rl=0,valid=1;i<3;i++){
            scanf("%lf %lf",&tri[i].l,&tri[i].a);
            if(tri[i].l!=-1.00000000)
                rl++;
            if(tri[i].a!=-1.00000000)
                ra++;
        }
        //too few conditions 
        if(rl+ra<3)
            valid=0;
        //test the given condition is accurate or not
        else
            valid=test(tri,rl,ra);
        if(!valid){
            printf("Invalid input.\n");
            continue;
        }
        //SSSAA
        if(rl==3&&ra==2){
            for(i=0;i<3;i++){
                if(tri[i].a==-1.00000000)
                    tri[i].a=countangle(tri);
            }
        }
        //SSAAA
        else if(rl==2&&ra==3){
            for(i=0;i<3;i++){
                if(tri[i].l==-1.00000000)
                    tri[i].l=cosvalue(tri,i);
            }
        }
        //SSAA
        else if(rl==2&&ra==2){
            for(i=0;i<3;i++){
                if(tri[i].a==-1.00000000)
                    tri[i].a=countangle(tri);
            }
            for(i=0;i<3;i++){
                if(tri[i].l==-1.00000000)
                    tri[i].l=cosvalue(tri,i);
            }
        }
        //SSA || SAS
        else if(rl==2&&ra==1){
            for(i=0;i<3;i++){
                if(tri[i].a!=-1.00000000)
                    temp=i;
            }
            //SAS unique
            if(tri[temp].l==-1.00000000){
                tri[temp].l=cosvalue(tri,temp);
                set_two_angle_by_sinvalue(tri,temp);
            }
            //SSA
            else{
                for(i=0;i<3;i++){
                    if(i!=temp&&tri[i].l!=-1.00000000)
                        y=i;
                }
                judge=ssa(tri,y,temp);
                if(judge==0){
                    printf("More than one solution.\n");
                    continue;
                }
                else if(judge<0){
                    printf("Invalid input.\n");
                    continue;
                }
            }
        }
        //AAS
        else if(rl==1&&ra==2){
            for(i=0;i<3;i++){
                if(tri[i].a==-1.00000000)
                    tri[i].a=countangle(tri);
            }
            set_two_side(tri);
        }
        //SAAA
        else if(rl==1&&ra==3){
            set_two_side(tri);
        }
        //SSSA
        else if(rl==3&&ra==1){
            for(i=0;i<3;i++){
                if(tri[i].a!=-1.00000000){
                    set_two_angle_by_sinvalue(tri,i);
                    break;
                }
            }
        }
        //SSS
        else if(rl==3&&ra==0){
            sss(tri);
        }
        //AAA
        else if(rl==0&&ra==3){
            printf("Invalid input.\n");
            continue;
        }
        valid=test(tri,3,3);
        if(valid){
            for(i=0;i<3;i++)
                printf("%.6lf %.6lf%c",tri[i].l,tri[i].a,i==2?'\n':' ');
        }
        else
            printf("Invalid input.\n");
    }
}

int test(struct set *s,int rl,int ra)
{
    int i;
    double array[3];
    double temp;
    const double pi=2*acos(0.0);
    //len and angle cannot be negetive
    for(i=0;i<3;i++){
        if((s[i].l!=-1.00000000&&s[i].l<=0.00000000)||(s[i].a!=-1.00000000&&s[i].a<=0.00000000))
            return 0;
    }
    //any len must larger than sum of the other two
    if(rl==3){
        for(i=0;i<3;i++)
            array[i]=s[i].l;
        qsort(array,3,sizeof(double),compare);
        if(array[0]>=array[1]+array[2])
            return 0;
    }
    //sum of three angles must equal to pi
    if(ra==3){
        for(i=0,temp=0.00000000;i<3;i++)
            temp+=s[i].a;
        if(fabs(pi-temp)>0.000001)
            return 0;
    }
    //if the info of angle is not complete, sum of these angles must smaller than pi
    else{
        for(i=0,temp=0.00000000;i<3;i++){
            if(s[i].a!=-1.00000000)
            temp+=s[i].a;
        }
        if(temp>=pi)
            return 0;
    }
    //test whether each len and angle is match or not
    for(i=0,temp=0.00000000;i<3;i++){
        if(s[i].l==-1.00000000||s[i].a==-1.00000000)
            continue;
        else if(temp==0.00000000)
            temp=s[i].l/sin(s[i].a);
        else{
            if(fabs(s[i].l/sin(s[i].a)-temp)>0.000001)
                return 0;
        }
    }
    return 1;
}

int compare(const void *f1,const void *f2)
{
    return *(double *)f1<*(double *)f2;
}

//given two angle, return the other value
double countangle(struct set *s)
{
       int i;
       const double pi=2*acos(0.0);
       double sum=0.00000000;
       for(i=0;i<3;i++){
           if(s[i].a!=-1.00000000)
               sum+=s[i].a;
       }
       return pi-sum;
}

//given two side of len and the middle angle, use cos value to evaluate the other len
double cosvalue(struct set *s,int n)
{
       int i,j;
       double side[2];
       for(i=0,j=0;i<3;i++){
           if(i!=n)
               side[j++]=s[i].l;
       }
       return sqrt(side[0]*side[0]+side[1]*side[1]-2*side[0]*side[1]*cos(s[n].a));;
}

void set_two_angle_by_sinvalue(struct set *s,int n)
{
     int i,j;
     //reverse of sin value
     const double r=sin(s[n].a)/s[n].l;
     const double pi=2*acos(0.0);
     double angle[2][2];
     int record[2];
     for(i=0,j=0;i<3;i++){
         if(i!=n){
             angle[j][0]=asin(r*s[i].l);
             angle[j][1]=pi-asin(r*s[i].l);
             record[j]=i;
             j++;
         }
     }
     if(fabs(s[n].a+angle[0][0]+angle[1][1]-pi)<0.000001){
         s[record[0]].a=angle[0][0];
         s[record[1]].a=angle[1][1];
     }
     else if(fabs(s[n].a+angle[0][1]+angle[1][0]-pi)<0.000001){
         s[record[0]].a=angle[0][1];
         s[record[1]].a=angle[1][0];
     }
     else{
         s[record[0]].a=angle[0][0];
         s[record[1]].a=angle[1][0];
     }
}


//handle SSA consition
int ssa(struct set *p,int side,int angle)
{
    const double pi=2*acos(0.0);
    int other;
    int i;
    if((p[angle].l<=p[side].l)&&(p[angle].a>=pi/2))
        return -1;
    else if((p[angle].l<p[side].l)&&(p[angle].a<pi/2)&&(p[side].l*sin(p[angle].a)>p[angle].l))
        return -1;
    else if((p[angle].l<p[side].l)&&(p[angle].a<pi/2)&&(p[side].l*sin(p[angle].a)<p[angle].l))
        return 0;
    p[side].a=asin((sin(p[angle].a)/p[angle].l)*p[side].l);
    for(i=0;i<3;i++){
        if(i!=side&&i!=angle)
            other=i;
    }
    p[other].a=countangle(p);
    p[other].l=cosvalue(p,other);
    return 1;
}

void set_two_side(struct set *p)
{
     int i;
     double sinv;
     for(i=0;i<3;i++){
         if(p[i].l!=-1.00000000)
             sinv=p[i].l/sin(p[i].a);
     }
     for(i=0;i<3;i++){
         if(p[i].l==-1.00000000)
             p[i].l=sinv*sin(p[i].a);
     }
}


//handle SSS condition
//use Heron area law to find sinvalue
void sss(struct set *p)
{
     int i,max;
     double d;
     double s=(p[0].l+p[1].l+p[2].l)/2;
     double area=sqrt(s*(s-p[0].l)*(s-p[1].l)*(s-p[2].l));
     const double pi=2*acos(0.0);
     //find the max
     for(i=0,d=0.00000000;i<3;i++){
         if(p[i].l>d){
             d=p[i].l;
             max=i;
         }
     }
     for(i=0,d=0.00000000;i<3;i++){
         if(i!=max)
             d+=(p[i].l)*(p[i].l);
     }
     for(i=0;i<3;i++){
         if(i!=max)
             p[i].a=value(p,2*area,i);
         else if(p[i].l*p[i].l<d)
             p[i].a=value(p,2*area,i);
         else
             p[i].a=pi-value(p,2*area,i);
     }
}

double value(struct set *p,double area,double n)
{
       int i;
       for(i=0;i<3;i++){
           if(i!=n)
               area/=p[i].l;
       }
       return asin(area);
}

thx for your help 

Code: Select all

removed, after acc..