Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<vector>
- #include <fstream>
- #include<string>
- #include<climits>
- #include<algorithm>
- #include<cmath>
- const int TABLE_SIZE = 999983;
- struct triangle {
- triangle(long long x, long long y, long long z) : a(x), b(y), c(z) {}
- triangle() : a(0), b(0), c(0) {}
- long long a;
- long long b;
- long long c;
- bool operator==(const triangle& other) const {
- if (a == other.a && other.b == b && c == other.c)
- return true;
- return false;
- }
- bool operator!=(const triangle& other) const {
- return !(*this == other);
- }
- };
- long long mod(long long a, long long b) {
- if (b < 0)
- return mod(-a, -b);
- long long ret = a % b;
- if (ret < 0)
- ret += b;
- return ret;
- }
- long long count_hash(triangle tr) {
- const long long p = 4294967295;
- const long long x = 877;
- long long hash = 0;
- hash = mod(
- mod(mod(tr.a * x, p) + mod(mod(tr.b * x, p)* x, p), p) +
- mod(mod(mod(tr.c * x, p)* x, p)* x, p), p);
- return hash;
- }
- long long GCD(long long a, long long b) {
- return b == 0 ? a : GCD(b, a % b);
- }
- long long find_GCD(long long a, long long b, long long c) {
- return GCD(GCD(a, b), c);
- }
- triangle canonical(triangle tr) {
- long long gcd = find_GCD(tr.a, tr.b, tr.c);
- if (gcd > 1) {
- tr.a /= gcd;
- tr.b /= gcd;
- tr.c /= gcd;
- }
- return tr;
- }
- class LinkedHashEntry {
- private:
- triangle key;
- int value;
- LinkedHashEntry *next;
- public:
- LinkedHashEntry(triangle key, int value) {
- this->key = key;
- this->value = value;
- this->next = NULL;
- }
- triangle getKey() {
- return key;
- }
- LinkedHashEntry *getNext() {
- return next;
- }
- void setNext(LinkedHashEntry *next) {
- this->next = next;
- }
- };
- class HashMap {
- private:
- LinkedHashEntry **table;
- public:
- long long counter = 0;
- HashMap() {
- table = new LinkedHashEntry*[TABLE_SIZE];
- for (int i = 0; i < TABLE_SIZE; ++i)
- table[i] = NULL;
- }
- void put(triangle key, int value) {
- int hash = (count_hash(key) % TABLE_SIZE);
- if (table[hash] == NULL) {
- table[hash] = new LinkedHashEntry(key, value);
- ++counter;
- } else {
- LinkedHashEntry *entry = table[hash];
- while (entry->getNext() != NULL)// && entry->getKey != key)
- entry = entry->getNext();
- if (entry->getKey() == key) {} // убрал getvalue
- else
- {
- entry->setNext(new LinkedHashEntry(key, value));
- ++counter;
- }
- }
- }
- ~HashMap() {
- for (int i = 0; i < TABLE_SIZE; ++i)
- if (table[i] != NULL) {
- LinkedHashEntry *prevEntry = NULL;
- LinkedHashEntry *entry = table[i];
- while (entry != NULL) {
- prevEntry = entry;
- entry = entry->getNext();
- delete prevEntry;
- }
- }
- delete[] table;
- }
- };
- int main() {
- HashMap hashMap;
- int n = 0;
- int a[3];
- long long num = 0;
- std::ifstream input("input.txt");
- std::ofstream output("output.txt");
- if (input.is_open())
- {
- input >> n;
- for (int i = 0; i < n; ++i) {
- input >> a[0];
- input >> a[1];
- input >> a[2];
- std::sort(a, a + 3);
- hashMap.put(canonical(triangle(a[0], a[1], a[2])), i);
- }
- }
- output << hashMap.counter;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement