Moderator: Board moderators
How can I work out with this problem. Help me please!!!
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
I think if the number of solutions is finite, then it's always either 0, 1 or 2.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).
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 1. Check if given data is correct: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.
Code: Select all
removed, after acc..