Thursday, 3 August 2017

Maximum Perimeter Triangle

This is a simple but tricky greedy problem. I find the solution without complicating the things in O(n logn), I hope you'll like this! . Check out the link below for the problem Description.
https://www.hackerrank.com/challenges/maximum-perimeter-triangle/problem


Solution:

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));
int cmpfunc (const void * a, const void * b)
{
   return (*(int*)b - *(int*)a);
}

int main() {

    int n,i,c=0;
    scanf("%d",&n);
    int a[n];
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);

    qsort(a, n, sizeof(int), cmpfunc);

    for(i=0;i<n-2;i++){
        if(a[i]<(a[i+1]+a[i+2])){
            c=1;
            printf("%d %d %d",a[i+2],a[i+1],a[i]);
            break;
        }
    }
    if(c==0)
        printf("-1");    
    return 0;
}

No comments:

Post a Comment