## 194 - Triangle

Moderator: Board moderators

krma
New poster
Posts: 3
Joined: Wed Aug 07, 2002 10:48 am

### 194 - Triangle I don't have any idea, how must i round up numbers in my program. My program work fine with the numbers, given by example, but judge dont want to acceppt my solution. I resume, that the problem is in rounding up numbers. How can I work out with this problem. Help me please!!!

krma
New poster
Posts: 3
Joined: Wed Aug 07, 2002 10:48 am

### A Realy Big Problem on 194

HI!

I'm working on program No.194 and I'll be realy happy for any hint or help by solving this program. I understand, that I have between 3-6 data which must I examine if they build a triangle and also caltucale data which not given by input.
Problem for me is:
I'dont know, how many different triangles can I build with 3,4,5 or 6 data - with the same numbers, but given by different number of input data (when i become a Invalid input or More solution or only a right data).
How can I know, which data and which equation is sufficient and not only needed.
Thanx 100x! krma
New poster
Posts: 3
Joined: Wed Aug 07, 2002 10:48 am

### 194 is the luckiest

HI!

I'm working on program No.194 and I'll be realy happy for any hint or help by solving this program.
I understand, that I have between 3-6 data which must I examine if they build a triangle and also caltucale data which not given by input.
Problem for me is:
I'dont know, how many different triangles can I build with 3,4,5 or 6 data - with the same numbers, but given by different number of input data (when i become a Invalid input or More solution or only a right data).
How can I know, which data and which equation is sufficient and not only needed.
Thanx 100x!

Orgi
New poster
Posts: 11
Joined: Mon Oct 29, 2001 2:00 am
Location: Bulgaria

### Re:

Well, the problem is not so hard.. you've got to see all the cases.. and determine the answer in each one

from elementary geometry it is known that a triangle is fully determined by:
1. three sides
2. two sides and the angle between them.
3. one side and two angles (the third is also known in this case, because the sum of all is Pi radians = 180 degrees)

so in either of these cases you only have to check if the other data is correct (or to add it if it is not given)
there is one case which could lead to 'More than one solution.'
and the number of solutions in this case is two..
it is when two sides and an angle are given but the angle is not between the sides.. in this case you have to make the calculations and see that there are one or two answers possible (for example cosine theorem on the given angle)
all other cases lead to 'Invalid input.'
good luck.

bugzpodder
Experienced poster
Posts: 147
Joined: Fri Jun 13, 2003 10:46 pm

### Help: 194 - WA [Resolved]

i am 99% i got all my cases covered but i am still getting WA. obviously i am missing something. anyone if you could point it out that would be great.

i made tolerances so that when i test for equality, i am actually testing the absolute value of diff<0.0000001
first i made sure all the angles and sides are valid (ie between 0 and pi, for angles, and sides satisfy triangle inequality, sum of angles is pi)
if i have less than 3 known or i know the 3 angles only, thats invalid
if i know two angles, figure out the 3rd angle
if i know SAAA, then it must be a unique (of course, valid) triangle. cosine law figure out the other two sides
if i know AAASS, use sine law to check if the two known sides over the sin of two known angles equal. if they arent, invalid. if they are, figure out the 3rd side and quit.
if i know AAASSS, i do the sine law again like the above case by checking equality for all three sides.
if i know SSS, then its unique triangle
if i know SSSA or SSSAA, figure out the other angle(s) using cosine law and see if the 3 angles sum up to pi
finally if we have SAS, then unique
if we have ASS, so we have opposite knowns side x and angle X, and another known side y.
if y>=x and X>=pi/2
invalid
if (y>x and X<pi/2 and x<y*sinX)
invalid
if (y>x and X<pi/2 and x>y*sinX)
more than one solution
otherwise there is a unique solution. determine angle B
using sine law, the 3rd angle using sum of angles, and 3rd side using cosine law

thats it. what am i missing?
Last edited by bugzpodder on Mon Aug 23, 2004 8:12 pm, edited 1 time in total.

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

### 194

There might be two problems:

1) Did you check that the sum of two angles must be lesser than PI?
2) If you have three sides, you don't have automatically a valid triangle;
e.g. c is 10 cm, a = 2 cm and b = 2 cm. You couldn't construct a
triangle with these data.

good luck

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
I don't get the second example. The information it gives is a = 62.72048064, alpha = 2.26853639, and beta = 0.56794657.

so, I calculate (from the angles summing to pi) gamma = .30510969...

Then I use c = a * sin(gamma)/sin(alpha) = 24.58722428...

So when I print it out I get 24.587224, which differs from the sample output which has 24.587225.

I'm using long doubles to store all the data. Am I doing something wrong? I didn't think that there's that much precision lost using sin(), and by using the equation with tan() I got the same wrong result. Can anyone explain?
I'm always willing to help, if you do the same.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
The problem asks to print answer with relative error less than 0.000001.
R.E. between 24.587224279... and 24.587225 is about .00000002932, so both answers should be accepted.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
Well, then I have no idea what my error is. Here's my convoluted code and reasoning about what it's supposed to do.

Here's the general idea of my code:

First I look for non-positive values, and if there are any, return "bad" which means to print invalid input.

Then I check that the angles don't sum to past pi, and the sides don't contradict the triangle inequality, if so I return bad;

then I look to see if I know all the sides, if so I call the SSS method, it calculates all the unknown angles (and checks if the input values contradict them). Thus I either know to return bad or return the actual values.

The rest of the code is similar. I look to see if I can use SAS next and then ASA (AAS is taken care of by ASA, since two angles give the third, so I don't need a function for that).

Since there are three possible angles to use for SAS I rotate the triangle three times (the for loop) and the pn array is used to do the rotation. I do a similar thing for ASA and SSA. I'm pretty sure this works right, since I've tested each of the three configurations on each of those. This way in the SAS method I can assume that a,alpha, and b are set correctly by the input (similarly for the other methods).

I'm less confident in my SSA method, it determines if there's no, one, or multiple solutions (by returning 0, 1, or 6 respectively). And I use http://www.andrews.edu/~calkins/math/we ... 07.htm#AAA for the general reasoning behind this method.

I'm guessing the problem is with precision somewhere, or a corner case that I just haven't stumbled upon.

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){

// 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]))
for(int i=1;i<v.size();i+=2)
if(angle(v[i]))

//side side side
if(used(v) && used(v) && used(v)){
if(sss(v,v,v,v,v,v))
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 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 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==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==1) return vector<long double>(1);
return v;
}
}

}``````
Last edited by Ryan Pai on Thu Mar 16, 2006 10:06 am, edited 1 time in total.
I'm always willing to help, if you do the same.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Your program doesn't seem to handle the SSA cases right. In the input

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
``````
all the triangles are ambiguous, so the six answers should be "More than one solution.", but your program just echoes the input (including the -1s).

I'm no expert on C++ (I'm less than a rookie, in fact), but should you not include <iostream> <cmath> and <vector>? I had to before it compiled on my machine...
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Ryan Pai
Learning poster
Posts: 67
Joined: Fri Jul 04, 2003 9:59 am
Location: USA
Contact:
Thanks Joey!

yeah, my problem was I was returning 2 instead of 1 from ssa (I had refactored my code like 7 different times, and forgot to change a constant).

(with the includes, I just didn't paste all my code).
I'm always willing to help, if you do the same.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I'm less confident in my SSA method, it determines if there's no, one, or multiple solutions (by returning 0, 1, or 6 respectively).
I think if the number of solutions is finite, then it's always either 0, 1 or 2.

Given two sides (say, a and b) and an angle not between them (beta), the law of sines gives sin(alpha). You'll have to guess whether alpha is acute or obtuse, but after that you know gamma=pi-alpha-beta, and so the triangle is uniquely determined.

peace
New poster
Posts: 5
Joined: Wed Aug 09, 2006 1:34 am

### 194 triangle WA plz help me

I cannot figure out why I always got WA

maybe I need more inputs to find the bug..

could someone help me ?

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;
//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;
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>=array+array)
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;
for(i=0,j=0;i<3;i++){
if(i!=n)
side[j++]=s[i].l;
}
return sqrt(side*side+side*side-2*side*side*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;
int record;
for(i=0,j=0;i<3;i++){
if(i!=n){
angle[j]=asin(r*s[i].l);
angle[j]=pi-asin(r*s[i].l);
record[j]=i;
j++;
}
}
if(fabs(s[n].a+angle+angle-pi)<0.000001){
s[record].a=angle;
s[record].a=angle;
}
else if(fabs(s[n].a+angle+angle-pi)<0.000001){
s[record].a=angle;
s[record].a=angle;
}
else{
s[record].a=angle;
s[record].a=angle;
}
}

//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.l+p.l+p.l)/2;
double area=sqrt(s*(s-p.l)*(s-p.l)*(s-p.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);
}

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: Re:

I got many WA.
Orgi wrote:Well, the problem is not so hard.. you've got to see all the cases.. and determine the answer in each one

from elementary geometry it is known that a triangle is fully determined by:
1. three sides
2. two sides and the angle between them.
3. one side and two angles (the third is also known in this case, because the sum of all is Pi radians = 180 degrees)

so in either of these cases you only have to check if the other data is correct (or to add it if it is not given)
there is one case which could lead to 'More than one solution.'
and the number of solutions in this case is two..
it is when two sides and an angle are given but the angle is not between the sides.. in this case you have to make the calculations and see that there are one or two answers possible (for example cosine theorem on the given angle)
all other cases lead to "Invalid input."
good luck.
1. Check if given data is correct:
a. One of sides or angles is zero
b. One of sides is greater or equal to sum of others, if 3 sides are given
d. One of angles or sum of two given angles greater or equal to pi
e. Sum of 3 angles doesn't equal to pi, if 3 angles are given
f. No sides are given
g. Number of given parameters (sides or angles) is less than 3

In all these cases print "Invalid input."

2. 3 sides are given:
a. Using Cosine law (or formula) check if given angles match or calculate them if unknown
b. If don't match print "Invalid input."

3. 3 angles are given (or two angles):
a. calculate third angle3 = pi - angle1 - angle2, if 2 angles are given.
b. Find one known side (There will be at least one known side)
c. Using Sine law (or formula) check if given sides match or calculate them if unknown.
d. If don't match print "Invalid input."

4. 2 sides and 1 angle are given
a. Find known angle.
b. If angle is between 2 given sides, calculate the side opposite of angle by Cosine law, other angles by Cosine law.
c. Side opposite to angle is given (let's call it x) and one other side is given (let's call it y):

If ( angle < pi/2 and x > y * sin(angle) ) print "More than one solution."
else
if ( angle >= pi/2 and x <= y ) print "Invalid input."
else
if ( angle < pi/2 and x < y * sin(angle) ) print "Invalid input."
else
There is unique solution, angle opposite to side y can be calculated by Sine law.
Third angle = pi - angle1 - angle2.
Third side can calculated by Cosine/Sine law.

What else i am missing?
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

lighted
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

### Re: 194 is the luckiest

``removed, after acc..``