Maximum Perimeter Triangle

  • + 1 comment

    C++ Solution (8/12 cases passed only)

    bool isPossibleTriangle(vector& sticks, int& i, int& j, int& k) { if( (sticks[i] + sticks[j] > sticks[k]) && (sticks[k] + sticks[j] > sticks[i]) && (sticks[i] + sticks[k] > sticks[j]) ) { return true ; } else return false ; }

    void solve(vector< pair< int,pair > >& triangles, vector& sticks, int pos1, int pos2, int pos3) { int size = sizeof(sticks)/ sizeof(sticks[0]) ; while(pos1 < size-2) { while(pos2 < size-1) { while(pos3 < size) { if(isPossibleTriangle(sticks, pos1, pos2, pos3)) { pair inner = make_pair(sticks[pos2],sticks[pos3]) ; pair > p = make_pair(sticks[pos1],inner) ; triangles.push_back(p) ; } pos3 ++ ; } pos2 ++ ; pos3 = pos2+1 ; } pos1 ++ ; pos2 = pos1 + 1 ; pos3 = pos2 + 1 ; } } vector maximumPerimeterTriangle(vector sticks) { int n = sticks.size() ;

    //Check for minimum sides
    vector <int> sidesOfAns ;
    if(n < 3)   {
        sidesOfAns.push_back(-1)    ;
        return sidesOfAns   ;
    }
    
    //Request for sorting sticks in non-decreasing
    bool  flag = 0  ;
    for(int i = 0; i < sticks.size()-1; i++)
    if(sticks[i] > sticks[i+1]) {
        flag = 1    ;
        break   ;
    }
    if(flag == 1)   {
        sort(sticks.begin(), sticks.end())   ;
    }
    
    
    //Request for making pairs of pairs of(three ) sticks for each triangle
    vector< pair< int,pair<int,int> > > triangles   ;
    solve(triangles, sticks, 0, 1, 2)   ;
    
    //Request for showing possible Triangles
    
    //Finding max perimeter && number of times max perimeter occurs && store 
    vector< pair< int,pair<int,int> > > possibleSolutios    ;
    int maxPeri = INT_MIN, maxPeriCount = 0 ;
    for(int i = 0; i < triangles.size(); i++)   {
        if( (triangles[i].first + triangles[i].second.first + triangles[i].second.second) > maxPeri)    {
            maxPeri = (triangles[i].first + triangles[i].second.first + triangles[i].second.second) ;
            //delete old saved possible maxima
            if(possibleSolutios.size() > 0) 
            possibleSolutios.clear()    ;
            //Make pairs of current three side values
            pair <int,int> inner = make_pair(triangles[i].second.first,triangles[i].second.second)  ;
            pair <int, pair<int,int> > p = make_pair(triangles[i].first, inner) ;
            //Save the pairs on possibleSolutios
            possibleSolutios.push_back(p)   ;
            maxPeriCount = 1    ;
        }
        else if( (triangles[i].first + triangles[i].second.first + triangles[i].second.second) == maxPeri ) {
            //Just save && increase count, count to check later for more problems
            pair <int,int> inner = make_pair(triangles[i].second.first,triangles[i].second.second)  ;
            pair <int, pair<int,int> > p = make_pair(triangles[i].first, inner) ;
            possibleSolutios.push_back(p)   ;
            maxPeriCount++  ;
        }
    }
    
    //Only one max sum of sides
    if(maxPeriCount == 1)   {
        sidesOfAns.push_back(possibleSolutios[0].first) ;
        sidesOfAns.push_back(possibleSolutios[0].second.first)  ;
        sidesOfAns.push_back(possibleSolutios[0].second.second) ;
        return sidesOfAns   ;
    }
    
    //Check for maximum side equality
    vector< pair< int,pair<int,int> > > possibleMaxEqualSolutions   ;
    int maxSideCount = 0, maxSide = INT_MIN ;
    for(int i = 0; i < maxPeriCount; i++)   {
    
        if(possibleSolutios[i].second.second > maxSide) {
            maxSide = possibleSolutios[i].second.second ;
    
            //delete old saved possible maxima
            if(possibleMaxEqualSolutions.size() > 0)    
            possibleMaxEqualSolutions.clear()   ;
    
            //Make pairs of current three side values
            pair <int,int> inner = make_pair( possibleSolutios[i].second.first, possibleSolutios[i].second.second ) ;
            pair <int, pair<int,int> > p = make_pair( possibleSolutios[i].first, inner) ;
    
            //Save the pairs on possibleMax(Side)EqualSolutios
            possibleMaxEqualSolutions.push_back(p)  ;
            maxSideCount = 1    ;
        }
        else if(possibleSolutios[i].second.second == maxSide)   {
    
            //Just save && increase count, count to check later for more problems
            pair <int,int> inner = make_pair( possibleSolutios[i].second.first, possibleSolutios[i].second.second ) ;
            pair <int, pair<int,int> > p = make_pair( possibleSolutios[i].first, inner )    ;
            possibleMaxEqualSolutions.push_back(p)  ;
            maxSideCount++  ;
        }
    }
    
    //Check how many triangles have equal max sides
    if(maxSideCount == 1)   {
        sidesOfAns.push_back(possibleMaxEqualSolutions[0].first)    ;
        sidesOfAns.push_back(possibleMaxEqualSolutions[0].second.first) ;
        sidesOfAns.push_back(possibleMaxEqualSolutions[0].second.second)    ;
        return sidesOfAns   ;
    }
    
    //Check for maximum side equality
    vector< pair< int,pair<int,int> > > possibleMaxMINEqualSolutions    ;
    int MINmaxSideCount = 0, MINmaxSide = INT_MAX   ;
    for(int i = 0; i < maxSideCount; i++)   {
    
        if(possibleMaxEqualSolutions[i].second.second < MINmaxSide) {
            MINmaxSide = possibleMaxEqualSolutions[i].second.second ;
    
            //delete old saved possible maxima
            if(possibleMaxMINEqualSolutions.size() > 0) 
            possibleMaxMINEqualSolutions.clear()    ;
    
            //Make pairs of current three side values
            pair <int,int> inner = make_pair( possibleMaxEqualSolutions[i].second.first, possibleMaxEqualSolutions[i].second.second )   ;
            pair <int, pair<int,int> > p = make_pair( possibleMaxEqualSolutions[i].first, inner)    ;
    
            //Save the pairs on possibleMax(Side)EqualSolutios
            possibleMaxMINEqualSolutions.push_back(p)   ;
            MINmaxSideCount = 1 ;
        }
        else if(possibleMaxEqualSolutions[i].second.second == MINmaxSide)   {
    
            //Just save && increase count, count to check later for more problems
            pair <int,int> inner = make_pair( possibleMaxEqualSolutions[i].second.first, possibleMaxEqualSolutions[i].second.second )   ;
            pair <int, pair<int,int> > p = make_pair( possibleMaxEqualSolutions[i].first, inner )   ;
            possibleMaxMINEqualSolutions.push_back(p)   ;
            MINmaxSideCount++   ;
        }
    }
    
    //Take any available minima + x + maxima (sided) triangle
    //Check how many triangles have equal max sides
    if(MINmaxSideCount >= 1)    {
        sidesOfAns.push_back(possibleMaxMINEqualSolutions[0].first) ;
        sidesOfAns.push_back(possibleMaxMINEqualSolutions[0].second.first)  ;
        sidesOfAns.push_back(possibleMaxMINEqualSolutions[0].second.second) ;
        return sidesOfAns   ;
    }
    else    {
        sidesOfAns.push_back(-1)    ;
        return sidesOfAns   ;
    }
    

    }