Maximum Perimeter Triangle

Sort by

recency

|

316 Discussions

|

  • + 0 comments

    Haskell

    module Main where
    
    import Data.List (find, sortBy)
    import Data.Maybe (fromMaybe)
    
    overlapping :: Int -> [a] -> [[a]]
    overlapping k xs
        | length xs < k = []
        | otherwise = take k xs : overlapping k (tail xs)
    
    solve :: [Int] -> [Int]
    solve xs = case firstValid of
        Just [x, y, z] -> [z, y, x]
        Nothing -> [-1]
      where
        xs' = sortBy (flip compare) $ filter (> 0) xs
        tripples = overlapping 3 xs'
        firstValid = find (\[x, y, z] -> x < y + z) tripples
    
    main :: IO ()
    main = do
        _ <- getLine
        xs <- map read . words <$> getLine :: IO [Int]
        putStrLn  $ unwords $ map show $ solve xs
    
  • + 0 comments

    Here is my c++ solution, you can watch the explanation here : https://youtu.be/cP4PLTgC1OE

    vector<int> maximumPerimeterTriangle(vector<int> sticks) {
        sort(sticks.begin(), sticks.end());
        for(int i = sticks.size() - 1; i >= 2; i--){
            if(sticks[i] < sticks[i - 1] + sticks[i - 2]) return {sticks[i - 2], sticks[i -1], sticks[i] };
        }
        return {-1};
    }
    
  • + 0 comments
    def maximumPerimeterTriangle(sticks):
        def nonDegenerateTriangle(t):
            return t[0] + t[1] > t[2]
    
        import itertools
        triangles = list(set(itertools.combinations(sticks, 3)))
    
        trueTriangles = [sorted(t) for t in triangles if nonDegenerateTriangle(sorted(t))]
    
        if not trueTriangles:
            return [-1]
        
        max_t2 = max(t[2] for t in trueTriangles)
        trueTriangles_t2 = [t for t in trueTriangles if t[2] == max_t2]
    
        max_t0 = max(t[0] for t in trueTriangles_t2)
        trueTriangles_t0 = [t for t in trueTriangles_t2 if t[0] == max_t0]
    
        return trueTriangles_t0[0]
    
  • + 0 comments

    include

    using namespace std;

    string ltrim(const string &); string rtrim(const string &); vector split(const string &);

    /* * Complete the 'maximumPerimeterTriangle' function below. * * The function is expected to return an INTEGER_ARRAY. * The function accepts INTEGER_ARRAY sticks as parameter. */

    vector maximumPerimeterTriangle(vector sticks) { int a=-1,b=-1,c=-1; sort(sticks.begin(),sticks.end(),greater()); int n=sticks.size(); for(int i=0;i

       for(int j=i+1;j<n-1;j++){
           for(int k=j+1;k<n;k++){
               int sum=sticks[j]+sticks[k];
               if(sum>sticks[i]){
                   int peri=a+b+c;
                   if(peri==-3)  a=sticks[i],b=sticks[j],c=sticks[k];
                   int nperi=sum+sticks[i];
                   if(nperi>peri){
                       a=sticks[i],b=sticks[j],c=sticks[k];
                   }
                   else if(nperi==peri){
                       if(a<sticks[i]){
                           a=sticks[i],b=sticks[j],c=sticks[k];
                       }
                       else if(a==sticks[i]){
                           if(c<sticks[k]){
                                a=sticks[i],b=sticks[j],c=sticks[k];
                           }
                       }
                   }
    
               }
           }
       }
    

    } if(a!=-1) return {c,b,a}; return {-1}; }

    int main() { ofstream fout(getenv("OUTPUT_PATH"));

    string n_temp;
    getline(cin, n_temp);
    
    int n = stoi(ltrim(rtrim(n_temp)));
    
    string sticks_temp_temp;
    getline(cin, sticks_temp_temp);
    
    vector<string> sticks_temp = split(rtrim(sticks_temp_temp));
    
    vector<int> sticks(n);
    
    for (int i = 0; i < n; i++) {
        int sticks_item = stoi(sticks_temp[i]);
    
        sticks[i] = sticks_item;
    }
    
    vector<int> result = maximumPerimeterTriangle(sticks);
    
    for (size_t i = 0; i < result.size(); i++) {
        fout << result[i];
    
        if (i != result.size() - 1) {
            fout << " ";
        }
    }
    
    fout << "\n";
    
    fout.close();
    
    return 0;
    

    }

    string ltrim(const string &str) { string s(str);

    s.erase(
        s.begin(),
        find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
    );
    
    return s;
    

    }

    string rtrim(const string &str) { string s(str);

    s.erase(
        find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
        s.end()
    );
    
    return s;
    

    }

    vector split(const string &str) { vector tokens;

    string::size_type start = 0;
    string::size_type end = 0;
    
    while ((end = str.find(" ", start)) != string::npos) {
        tokens.push_back(str.substr(start, end - start));
    
        start = end + 1;
    }
    
    tokens.push_back(str.substr(start));
    
    return tokens;
    

    }

  • + 0 comments

    Java

    public static List<Integer> maximumPerimeterTriangle(List<Integer> sticks) {
        // Write your code here
            List<Integer> ans = new ArrayList<>();
            int x = -1;
            Collections.sort(sticks);
            for(int i =0; i<sticks.size()-2; i++)
                if(sticks.get(i)+sticks.get(i+1) > sticks.get(i+2))
                    x = i;
            if(x== -1){
                ans.add(-1);
                return ans;
            } else {
                ans.add(sticks.get(x));
                ans.add(sticks.get(x+1));
                ans.add(sticks.get(x+2));
                return ans;
            }
        }