You are viewing a single comment's thread. Return to all comments →
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 ; }
}
Seems like cookies are disabled on this browser, please enable them to open this website
Maximum Perimeter Triangle
You are viewing a single comment's thread. Return to all comments →
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() ;
}