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.

Powered By
CHP Adblock Detector Plugin | Codehelppro