#include <stdio.h>

#include <stdlib.h>

#include <string.h>

/*Struct defining cube*/

typedef struct

{

int l;

int b;

int h;

}Cube;

/*Cube compare function */

int cube_compare(const void *x, const void *y)

{

const Cube *a = x;

const Cube *b = y;

if(a->l == b->l)

{

if(a->b == b->b)

return a->h - b->h;

return a->b - b->b;

}

return a->l - b->l;

}

/*Struct to hold successor info*/

typedef struct

{

int next;

int chainLength;

}Successor;

/*Checks whether cube 'a' fits into cube 'b' */

inline int cube_fits(Cube *a , Cube *b)

{

return (a->l < b-> l) && (a->b < b->b) && (a->h < b->h);

}

/*Prints all the cubes which fits into one another */

void max_fit_cubes(Cube cubes[], int n)

{

//Fill the chain

Successor nextCube[n];

memset(nextCube, 0, sizeof(nextCube));

int i = n - 1, j;

while(i--)

{

for(j = i + 1; j < n; j++)

{

if(cube_fits(cubes + i, cubes + j))

{

if((nextCube[j].chainLength + 1) > nextCube[i].chainLength)

{

nextCube[i].chainLength = nextCube[j].chainLength + 1;

nextCube[i].next = j;

}

}

}

}

//find the max chain

int m = i = n - 1;

while(i--)

{

if(nextCube[i].chainLength > nextCube[m].chainLength)

m = i;

}

//Now print the max chain

printf("Max Chain Length: %d, m: %d\n", nextCube[m].chainLength, m);

do

{

printf("(%d,%d,%d) =>", cubes[m].l, cubes[m].b, cubes[m].h);

m = nextCube[m].next;

}while(m);

printf("\n");

}

int main()

{

int n;

scanf("%d", &n);

Cube cubes[n];

int i;

for(i = 0; i < n; ++i)

{

scanf("%d%d%d", &(cubes[i].l), &(cubes[i].b), &(cubes[i].h));

}

qsort(cubes, n, sizeof(Cube), cube_compare);

max_fit_cubes(cubes, n);

return 0;

}

Advertisements
(function(){var c=function(){var a=document.getElementById("crt-1143366223");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:388248,containerid:"crt-1143366223",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();
(function(){var c=function(){var a=document.getElementById("crt-274962333");window.Criteo?(a.parentNode.style.setProperty("display","inline-block","important"),a.style.setProperty("display","block","important"),window.Criteo.DisplayAcceptableAdIfAdblocked({zoneid:837497,containerid:"crt-274962333",collapseContainerIfNotAdblocked:!0,callifnotadblocked:function(){a.style.setProperty("display","none","important");a.style.setProperty("visbility","hidden","important")}})):(a.style.setProperty("display","none","important"),a.style.setProperty("visibility","hidden","important"))};if(window.Criteo)c();else{if(!__ATA.criteo.script){var b=document.createElement("script");b.src="//static.criteo.net/js/ld/publishertag.js";b.onload=function(){for(var a=0;a<__ATA.criteo.cmd.length;a++){var b=__ATA.criteo.cmd[a];"function"===typeof b&&b()}};(document.head||document.getElementsByTagName("head")[0]).appendChild(b);__ATA.criteo.script=b}__ATA.criteo.cmd.push(c)}})();