194 - Triangle

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 194 is the luckiest

Post by brianfry713 » Mon Jul 14, 2014 9:33 pm

Input:

Code: Select all

1
-1.00000000 -1.00000000 45.51570132 -1.00000000 80.21764072 2.32123470
AC output:

Code: Select all

41.944135 0.392423 45.515701 0.427935 80.217641 2.321235
Check input and AC output for thousands of problems on uDebug!

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

Re: 194 is the luckiest

Post by lighted » Tue Jul 15, 2014 11:57 am

Thanks Brianfry!

If fixed my bug. I forgot to take sqrt of side when calculate it by cosine law.
But i still get WA.
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 194 is the luckiest

Post by brianfry713 » Tue Jul 15, 2014 8:23 pm

Input:

Code: Select all

1
-1.00000000 -1.00000000 81.04284300 -1.00000000 83.34672734 0.05282544
AC output:

Code: Select all

164.166600 3.037403 81.042843 0.051364 83.346727 0.052825
Check input and AC output for thousands of problems on uDebug!

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

Re: 194 is the luckiest

Post by lighted » Tue Jul 15, 2014 9:27 pm

Thank you very muuuuuuuuuuuuch! :lol: :lol: :lol:
I got acc. Uhunt shows my rank at 15.

This part was wrong
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."
Correct is

Code: Select all

If ( angle < pi/2 and x < y  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."
Also i got WA with eps = 1e-8.
I changed it to 1e-6 and got acc. :wink:
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

LlatzerandToni
New poster
Posts: 15
Joined: Sun Apr 23, 2006 1:35 pm

Re: 194 - Triangle

Post by LlatzerandToni » Thu Mar 26, 2015 10:42 am

I don't know why I am getting WA... Help, please?

Code: Select all

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <list>
#include <queue>
#include <sstream>
#include <stack>
#include <stdio.h>
#include <string>
#include <vector>

using namespace std;

double tol = 0.000001;
vector<double> p(7,0);

bool fail_test (int i) {
     if (i==2) {
        if (p[1]==-1.) {
           p[1] = M_PI - p[3] - p[5];
           if (p[1] < 0)
              return true;
        }
        else if (p[3]==-1.) {
             p[3] = M_PI - p[1] - p[5];
             if (p[3] < 0)
                return true;
        }
        else if (p[5]==-1.) {
             p[5] = M_PI - p[1] - p[3];
             if (p[5] < 0)
                return true;
        }
     }
     if (p[1]!=-1. and p[3]!=-1. and p[5]!=-1. and abs(p[1]+p[3]+p[5]-M_PI)>tol)
        return true;
     if (p[0]!=-1. and p[1]!=-1. and p[2]!=-1. and p[3]!=-1. and abs(p[0]*sin(p[3])-p[2]*sin(p[1]))>tol)
        return true;
     if (p[0]!=-1. and p[1]!=-1. and p[4]!=-1. and p[5]!=-1. and abs(p[0]*sin(p[5])-p[4]*sin(p[1]))>tol)
        return true;
     if (p[4]!=-1. and p[5]!=-1. and p[2]!=-1. and p[3]!=-1. and abs(p[4]*sin(p[3])-p[2]*sin(p[5]))>tol)
        return true;
     if (p[0]!=-1. and p[1]!=-1. and p[2]!=-1. and p[4]!=-1. and abs(p[2]*p[2]+p[4]*p[4]-2*p[2]*p[4]*cos(p[1])-p[0]*p[0])>tol)
        return true;
     if (p[0]!=-1. and p[2]!=-1. and p[3]!=-1. and p[4]!=-1. and abs(p[0]*p[0]+p[4]*p[4]-2*p[0]*p[4]*cos(p[3])-p[2]*p[2])>tol)
        return true;
     if (p[0]!=-1. and p[2]!=-1. and p[4]!=-1. and p[5]!=-1. and abs(p[2]*p[2]+p[0]*p[0]-2*p[0]*p[2]*cos(p[5])-p[4]*p[4])>tol)
        return true;
     return false;
}

vector<double> caseA () {
   int k=0;
   vector<double> q = p;
   if (q[1]==-1.)
      q[1] = M_PI - q[3] - q[5];
   else if (q[3]==-1.)
        q[3] = M_PI - q[1] - q[5];
   else
       q[5] = M_PI - q[1] - q[3];
   if (q[0]==-1. and q[2]==-1.) {
      q[0] = q[4]*sin(q[1])/sin(q[5]);
      q[2] = q[4]*sin(q[3])/sin(q[5]);
   }
   else if (q[0]==-1. and q[4]==-1.) {
      q[0] = q[2]*sin(q[1])/sin(q[3]);
      q[4] = q[2]*sin(q[5])/sin(q[3]);
   }
   else {
        q[2] = q[0]*sin(q[3])/sin(q[1]);
        q[4] = q[0]*sin(q[5])/sin(q[1]);
   }
   return q;
}

vector<double> caseB() {
   vector<double> q = p;
   if (q[0]!=-1. and q[1]!=-1.) {
      if (q[2]!=-1.) {
         if (q[1] < M_PI/2 and q[0] < q[2] and q[0] > q[2]*sin(q[1]))
            q[6] = -2;
         else if (q[1] >= M_PI/2 and q[0] <= q[2] or q[1] < M_PI/2 and q[0] < q[2]*sin(q[1]))
             q[6] = -1;
         else {
            q[3] = asin(q[2]*sin(q[1])/q[0]);
            q[5] = M_PI - q[1] - q[3];
            q[4] = q[0]*sin(q[5])/sin(q[1]);
         }
      }
      else {
         if (q[1] < M_PI/2 and q[0] < q[4] and q[0] > q[4]*sin(q[1]))
            q[6] = -2;
         else if (q[1] >= M_PI/2 and q[0] <= q[4] or q[1] < M_PI/2 and q[0] < q[4]*sin(q[1]))
             q[6] = -1;
         else {
            q[5] = asin(q[4]*sin(q[1])/q[0]);
            q[3] = M_PI - q[1] - q[5];
            q[2] = q[0]*sin(q[3])/sin(q[1]);
         }
      }
   }
   else if (q[2]!=-1. and q[3]!=-1.) {
      if (q[0]!=-1.) {
         if (q[3] < M_PI/2 and q[2] < q[0] and q[2] > q[0]*sin(q[3]))
            q[6] = -2;
         else if (q[3] >= M_PI/2 and q[2] <= q[0] or q[3] < M_PI/2 and q[2] < q[0]*sin(q[3]))
             q[6] = -1;
         else {
            q[1] = asin(q[0]*sin(q[3])/q[2]);
            q[5] = M_PI - q[1] - q[3];
            q[4] = q[2]*sin(q[5])/sin(q[3]);
         }
      }
      else {
         if (q[3] < M_PI/2 and q[2] < q[4] and q[2] > q[4]*sin(q[3]))
            q[6] = -2;
         else if (q[3] >= M_PI/2 and q[2] <= q[4] or q[3] < M_PI/2 and q[2] < q[4]*sin(q[3]))
             q[6] = -1;
         else {
            q[5] = asin(q[4]*sin(q[3])/q[2]);
            q[1] = M_PI - q[5] - q[3];
            q[0] = q[2]*sin(q[1])/sin(q[3]);
         }
      }
   }
   else if (q[4]!=-1. and q[5]!=-1.) {
      if (q[0]!=-1.) {
         if (q[5] < M_PI/2 and q[4] < q[0] and q[4] > q[0]*sin(q[5]))
            q[6] = -2;
         else if (q[5] >= M_PI/2 and q[4] <= q[0] or q[5] < M_PI/2 and q[4] < q[0]*sin(q[5]))
             q[6] = -1;
         else {
            q[1] = asin(q[0]*sin(q[5])/q[4]);
            q[3] = M_PI - q[1] - q[5];
            q[2] = q[4]*sin(q[3])/sin(q[5]);
         }
      }
      else {
         if (q[5] < M_PI/2 and q[4] < q[2] and q[4] > q[2]*sin(q[5]))
            q[6] = -2;
         else if (q[5] >= M_PI/2 and q[4] <= q[2] or q[5] < M_PI/2 and q[4] < q[2]*sin(q[5]))
             q[6] = -1;
         else {
            q[3] = asin(q[2]*sin(q[5])/q[4]);
            q[1] = M_PI - q[3] - q[5];
            q[0] = q[4]*sin(q[1])/sin(q[5]);
         }
      }
   }
   return q;
}

vector<double> caseC() {
   vector<double> q = p;
   if (q[0]==-1.) {
      q[0] = sqrt(q[2]*q[2] + q[4]*q[4] - 2*q[2]*q[4]*cos(q[1]));
      if (q[2] < q[4]) {
         q[3] = asin(q[2]*sin(q[1])/q[0]);
         q[5] = M_PI - q[1] - q[3];
      }
      else {
         q[5] = asin(q[4]*sin(q[1])/q[0]);
         q[3] = M_PI - q[1] - q[5];
      }
   }
   else if (q[2]==-1.) {
      q[2] = sqrt(q[0]*q[0] + q[4]*q[4] - 2*q[0]*q[4]*cos(q[3]));
      if (q[0] < q[4]) {
         q[1] = asin(q[0]*sin(q[3])/q[2]);
         q[5] = M_PI - q[1] - q[3];
      }
      else {
         q[5] = asin(q[4]*sin(q[3])/q[2]);
         q[1] = M_PI - q[5] - q[3];
      }
   }
   else if (q[4]==-1.) {
      q[4] = sqrt(q[0]*q[0] + q[2]*q[2] - 2*q[0]*q[2]*cos(q[5]));
      if (q[0] < q[2]) {
         q[1] = asin(q[0]*sin(q[5])/q[4]);
         q[3] = M_PI - q[1] - q[5];
      }
      else {
         q[3] = asin(q[2]*sin(q[5])/q[4]);
         q[1] = M_PI - q[3] - q[5];
      }
   }
   return q;
}

vector<double> caseD() {
   double tmp;
   vector<double> q = p;
   tmp = (q[2]*q[2] + q[4]*q[4] - q[0]*q[0]) / (2*q[2]*q[4]);
   if (abs(q[2]*q[2] + q[4]*q[4] - q[0]*q[0]) > 2*q[2]*q[4]) {
      q[6] = -1;
   }
   else {
        if (q[0]<q[2] and q[0]<q[4]) {
           q[1] = acos((q[2]*q[2] + q[4]*q[4] - q[0]*q[0]) / (2*q[2]*q[4]));
           if (q[2]<q[4]) {
              q[3] = asin(q[2]*sin(q[1])/q[0]);
              q[5] = M_PI - q[1] - q[3];
           }
           else {
              q[5] = asin(q[4]*sin(q[1])/q[0]);
              q[3] = M_PI - q[1] - q[5];
           }
        }
        else if (q[2]<q[0] and q[2]<q[4]) {
             q[3] = acos((q[0]*q[0] + q[4]*q[4] - q[2]*q[2]) / (2*q[0]*q[4]));
             if (q[0]<q[4]) {
                q[1] = asin(q[0]*sin(q[3])/q[2]);
                q[5] = M_PI - q[1] - q[3];
             }
             else {
                q[5] = asin(q[4]*sin(q[3])/q[2]);
                q[1] = M_PI - q[5] - q[3];
             }
        }
        else {
             q[5] = acos((q[0]*q[0] + q[2]*q[2] - q[4]*q[4]) / (2*q[0]*q[2]));
             if (q[0]<q[2]) {
                q[1] = asin(q[0]*sin(q[5])/q[4]);
                q[3] = M_PI - q[1] - q[5];
             }
             else {
                q[3] = asin(q[2]*sin(q[5])/q[4]);
                q[1] = M_PI - q[3] - q[5];
             }
        }
   }
   return q;
}

vector<double> play () {
     int k, lk = 0, ak = 0;
     vector<double> q (7);
     
     for (k=0; k<6; ++k) {
         if (p[k]!=-1.) {
            if (k%2==0)
               ++lk;
            else
                ++ak;
         }
     }
     
     if (lk == 0 or lk+ak < 3 or fail_test(ak)) {
        q[6] = -1;
        return q;
     }
     if (lk == 1 and ak >= 2)
        return caseA();
     if (lk == 2 and ak >= 1) {
        if (p[0]!=-1. and p[1]!=-1. or p[2]!=-1. and p[3]!=-1. or p[4]!=-1. and p[5]!=-1.) {
           return caseB();
        }
        else {
             return caseC();
        }
     }
     if (lk == 3)
        return caseD();
}

int main()
{
    int n, k;
    bool b;
    vector<double> q;
    cin >> n;
    while (n>0) {
          for (int i=0; i<6; ++i)
              cin >> p[i];
          q = play ();
          if (q[6]==-1.)
             cout << "Invalid input." << endl;
          else if (q[6]==-2.) {
               cout << "More than one solution." << endl;
          }
          else {
               b = true;
               for (int i=0; i<6; ++i){
                   if (not b)
                      cout << ' ';
                   else
                       b = false;
                   printf("%.6f",q[i]);
               }
               printf("\n");
          }
          --n;
    }
}
Lol

LlatzerandToni
New poster
Posts: 15
Joined: Sun Apr 23, 2006 1:35 pm

Re: 194 - Triangle

Post by LlatzerandToni » Mon Apr 27, 2015 2:06 pm

I found my error, but I can't edit the post to delete code.

Input:

Code: Select all

1
52.3790777315 0.9137932778 57.2377418870 -1.0000000000 -1.0000000000 1.1820993541
Otuput:

Code: Select all

52.379078 0.913793 57.237742 1.045700 61.215192 1.182099
Lol

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 194 - Triangle

Post by metaphysis » Wed Mar 16, 2016 11:52 am

WA again and again. Could anyone point out my error?

Code: Select all

#include <iostream>
#include <iomanip>
#include <map>
#include <cmath>

using namespace std;

const double EPSILON = 1E-7;
const double PI = 3.14159265358979323846;
const double HALF_PI = PI / 2.0;

map < char, double > paras;
map < char, bool > defined;
string variable = "aAbBcC";
bool multiSolution = false;

double acos(double a, double b, double c)
{
    return acos((a * a + b * b - c * c) / (2 * a * b));
}

bool calculate()
{
    if (defined['a'] && defined['b'] && defined['c'])
    {
        if (paras['a'] + paras['b'] <= paras['c'] ||
            paras['b'] + paras['c'] <= paras['a'] ||
            paras['a'] + paras['c'] <= paras['b'])
            return false;

        double temp = acos(paras['b'], paras['c'], paras['a']);
        if (defined['A'] == false)
            paras['A'] = temp;
        else if (abs(temp - paras['A']) > EPSILON)
            return false;
        
        temp = acos(paras['a'], paras['c'], paras['b']);
        if (defined['B'] == false)
            paras['B'] = temp;
        else if (abs(temp - paras['B']) > EPSILON)
            return false;

        temp = acos(paras['a'], paras['b'], paras['c']);
        
        if (defined['C'] == false)
            paras['C'] = temp;
        else if (abs(temp - paras['C']) > EPSILON)
            return false;

        return true;
    }
    
    if (defined['A'] && defined['B'] && defined['C'])
    {
        if (abs(paras['A'] + paras['B'] + paras['C'] - PI) > 1E-4)
            return false;
    }
    else
    {
        string angles[] = {"ABC", "ACB", "BCA"};
        for (int i = 0; i < 3; i++)
        {
            string v = angles[i];
            
            if (defined[v[0]] && paras[v[0]] >= PI ||
                defined[v[1]] && paras[v[1]] >= PI ||
                defined[v[2]] && paras[v[2]] >= PI)
                return false;
                               
            if (defined[v[0]] && defined[v[1]] && !defined[v[2]])
            {
                if (paras[v[0]] + paras[v[1]] >= PI)
                    return false;
                    
                paras[v[2]] = PI - paras[v[0]] - paras[v[1]];
                defined[v[2]] = true;
                break;
            }
        }
    }
    

    if (defined['A'] && defined['B'] && defined['C'])
    {
        if (!defined['a'] && !defined['b'] && !defined['c'])
            return false;

        string sideAngles[] = {"aABCbc", "bBACac", "cCABab"};
        for (int i = 0; i < 3; i++)
        {
            string v = sideAngles[i];
            if (defined[v[0]])
            {
                double temp = paras[v[0]] / sin(paras[v[1]]) * sin(paras[v[2]]);
                
                if (defined[v[4]] == false)
                    paras[v[4]] = temp;
                else if (abs(temp - paras[v[4]]) > EPSILON)
                    return false;

                temp = paras[v[0]] / sin(paras[v[1]]) * sin(paras[v[3]]);
                if (defined[v[5]] == false)
                    paras[v[5]] = temp;
                else if (abs(temp - paras[v[5]]) > EPSILON)
                    return false;

                return true;
            }
        }
    }

    string cosines[] = {"abCcAB", "acBbAC", "bcAaBC"};
    for (int i = 0; i < 3; i++)
    {
        string v = cosines[i];
        if (defined[v[0]] && defined[v[1]] && defined[v[2]])
        {
            double temp = sqrt(paras[v[0]] * paras[v[0]] +
                paras[v[1]] * paras[v[1]] - 2 * paras[v[0]] * paras[v[1]] * cos(paras[v[2]]));
            
            if (defined[v[3]] == false)
                paras[v[3]] = temp;
            else if (abs(temp - paras[v[3]]) > EPSILON)
                return false;

            temp = asin(paras[v[0]] / paras[v[3]] * sin(paras[v[2]]));
            if (defined[v[4]] == false)
                paras[v[4]] = temp;
            else if (abs(temp - paras[v[4]]) > EPSILON)
                return false;
                
            temp = PI - paras[v[2]] - paras[v[4]];
            if (defined[v[5]] == false)
                paras[v[5]] = temp;
            else if (abs(temp - paras[v[5]]) > EPSILON)
                return false;
            
            return true;
        }
    }

    string sines[] = { "abABCc", "baBACc", "acACBb", "caCABb", "bcBCAa", "cbCBAa" };
    for (int i = 0; i < 6; i++)
    {
        string v = sines[i];
        if (defined[v[0]] && defined[v[1]] && defined[v[2]])
        {
            if (paras[v[2]] >= HALF_PI && paras[v[0]] < paras[v[1]])
                return false;
                
            if (paras[v[2]] < HALF_PI && paras[v[0]] < (paras[v[1]] * sin(paras[v[2]])))
                return false;
            
            if (paras[v[2]] < HALF_PI &&
                paras[v[0]] < paras[v[1]] &&
                paras[v[0]] > (paras[v[1]] * sin(paras[v[2]])))
            {
                multiSolution = true;
                return true;
            }
  
            paras[v[3]] = asin(paras[v[1]] / paras[v[0]] * sin(paras[v[2]]));
            paras[v[4]] = PI - paras[v[2]] - paras[v[3]];
            paras[v[5]] = paras[v[0]] / sin(paras[v[2]]) * sin(paras[v[4]]);
                           
            return true;
        }
    }
    
    return false;
}

int main(int argc, char *argv[])
{
    int n;
    double temp;
    
    cin >> n;
    while (n--)
    {
        bool valid = true;
        int counter = 0;
        multiSolution = false;
        
        for (int i = 0; i < variable.length(); i++)
        {
            cin >> temp;
            paras[variable[i]] = temp;
            if (temp > 0.0)
            {
                defined[variable[i]] = true;
                counter++;
            }
            else if (temp == -1.0)
            {
                defined[variable[i]] = false;
            }
            else
            {
                valid = false;
            }
        }

        if (counter <= 2)
            valid = false;
            
        if (valid == false || calculate() == false)
        {
            cout << "Invalid input.\n";
        }
        else if (multiSolution == true)
        {
            cout << "More than one solution.\n";
        }
        else
        {
            for (int i = 0; i < variable.length(); i++)
                cout << (i > 0 ? " " : "") << fixed << setprecision(6) << paras[variable[i]];
            cout << "\n";
        }
    }

    return 0;
}

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 194 - Triangle

Post by metaphysis » Thu Mar 24, 2016 5:17 pm

I found my bug by myself.

Post Reply

Return to “Volume 1 (100-199)”