Triangle Games

QUESTION

You are given n triangles.\n\nYou are required to find how many triangles are unique out of given triangles. For each triangle you are given three integers a,b,c , the sides of a triangle.\n\nA triangle is said to be unique if there is no other triangle with same set of sides.\n\nNote : It is always possible to form triangle with given sides.\n\nINPUT:\n\nFirst line contains n, the number of triangles. Each of next n lines contain three integers a,b,c (sides of a triangle).\n\nOutput:\n\nprint single integer, the number of unique triangles.

“TESTCASE_1”: “5\n7 6 5\n5 7 6\n8 2 9\n2 3 4\n2 4 3\n###—###SEPERATOR—###—\n1”, “TESTCASE_2”: “4\n1574 5033 3460\n3329 9634 6306\n3460 1574 5033\n7719 13529 5811\n###—###SEPERATOR—###—\n2”, “TESTCASE_3”: “3\n8046 1647 8432\n8432 8046 1647\n4120 1191 7791\n###—###SEPERATOR—###—\n1”, “TESTCASE_4”: “0\n###—###SEPERATOR—###—\n0”, “TESTCASE_5”: “0\n###—###SEPERATOR—###—\n0

ANSWER

#include<stdio.h>
void swap(long long int *a, long long int *b)
{
 	 long long int t;
 	 t=*a;
 	 *a=*b;
 	 *b=t;
}
 
void qsort(long long int items[][4], long long int left, long long int right)
{
     register long long int i,j,k;
     long long int x, y;
     
     i = left; j = right;
     x = items[(left+right)/2][3];
     do 
     {
        while((items[i][3] < x) && (i < right)) 
           i++;
        while((x < items[j][3]) && (j > left))
           j--;
        if(i <= j) 
        {
             y = items[i][0];items[i][0] = items[j][0];items[j][0] = y;
			 y = items[i][1];items[i][1] = items[j][1];items[j][1] = y;
			 y = items[i][2];items[i][2] = items[j][2];items[j][2] = y;
			 y = items[i][3];items[i][3] = items[j][3];items[j][3] = y;
             i++;
             j--;
        }
     } while(i <= j);
 
     if(left < j) 
             qsort(items, left, j);
     if(i < right) 
             qsort(items, i, right);
}
 
int main()
{
    long long int i,k,j,n,z,g,count=0;
    long long int p,q,r;
    long long int arr[100000][4]={0};
    scanf("%lld",&n);
    for(i=0;i<n;i++)
    {
            scanf("%lld %lld %lld",&arr[i][0],&arr[i][1],&arr[i][2]);
            arr[i][3]=arr[i][0]+arr[i][1]+arr[i][2];
            if (arr[i][0] > arr[i][1]) swap(&arr[i][0],&arr[i][1]);
			if (arr[i][1] > arr[i][2]) swap(&arr[i][1],&arr[i][2]);
			if (arr[i][0] > arr[i][1]) swap(&arr[i][0],&arr[i][1]);
    }
    qsort(arr,0,n-1);
    i=0;
    while(1)
    {
	 		p=arr[i][0];
	 		q=arr[i][1];
	 		r=arr[i][2];
	 		k=arr[i][3];
	 		j=i;
	 		z=0;
	 		if(p==0)
	   		{
			 		++i;
			 		if(i==n)
			 		    break;
   			        else
			 			continue;
	 		}
			while(arr[++i][3]==k && i<n)
			{
			 					 if(arr[i][0]!=0 && arr[i][0]==p && arr[i][1]==q && arr[i][2]==r)
			 					 {
	                                arr[i][0]=0;
			 					    z++;
							     }
		 	}
		 	if(z!=i-1-j && z>=1)
		 	{
		            i=j+1;
		            continue;
			}
			else if(z==0)
			{
			        count++;
			        if(i!=j+1)
			        {
			        		  i=j+1;
			        		  continue;  
	                }	  
			}
            if(i==n)
            		break;
	}
    printf("%lld",count);
    return 0;
}
Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.