Orange-Bloom/counting-triangles.java at master · aky91/Orange-Bloom · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
// Akash Yadav
// @Hudson Lane, Delhi
// 19th June 18

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

class TestClass{

	//https://www.hackerearth.com/practice/algorithms/searching/binary-search/practice-problems/algorithm/counting-triangles/

	public static Scanner scn = new Scanner(System.in);

	public static long prime = 10000000002065383L;

	public static void main (String[] args) throws java.lang.Exception{

		int N = scn.nextInt();

		long[][] points = new long[N][3];

		long[][] hash = new long[N][2];

		for(int i = 0; i < N; i++){

			long a = scn.nextLong();
			long b = scn.nextLong();
			long c = scn.nextLong();

			points[i][0] = a;
			points[i][1] = b;
			points[i][2] = c;

			long hashVal = getHash(a, b, c);

			hash[i][0] = hashVal;
			hash[i][1] = i;
		}

		Arrays.sort(hash, new Comparator<long[]>(){

			@Override
			public int compare(long[] a, long[] b){

				if(a[0] < b[0])	return -1;

				if(a[0] > b[0])	return 1;

				return 0;
			}
		});

		int count = 0;

		for(int i = 0; i < N;){

			int range = 0;

			while((i + range) < N && hash[i + range][0] == hash[i][0])
				range++;

			if(range == 1){
				count++;
				i++;
				continue;
			}

			i += range;
		}

		System.out.println(count);

	}

	public static long getHash(long a, long b, long c){

		long hash = (a%prime + b%prime + c%prime + (a*b)%prime + (b*c)%prime + (a*c)%prime + (a*b*c)%prime)%prime;

		return hash;
	}

	public static boolean areTheseTrianglesSame(int i, int j, long[][] arr){

		long[] arr1 = {arr[i][0], arr[i][1], arr[i][2]};
		Arrays.sort(arr1);

		long[] arr2 = {arr[j][0], arr[j][1], arr[j][2]};
		Arrays.sort(arr2);

		if(arr1[0] == arr2[0] && arr1[1] == arr2[1] && arr1[2] == arr2[2])
			return true;

		return false;
	}

}