Advertisement
Guest User

d

a guest
Dec 9th, 2016
72
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.72 KB | None | 0 0
  1. #include<iostream>
  2. #include<vector>
  3. #include <fstream>
  4. #include<string>
  5. #include<climits>
  6. #include<algorithm>
  7. #include<cmath>
  8.  
  9. const int TABLE_SIZE = 999983;
  10.  
  11.  
  12. struct triangle {
  13.     triangle(long long x, long long y, long long z) : a(x), b(y), c(z) {}
  14.     triangle() : a(0), b(0), c(0) {}
  15.     long long a;
  16.     long long b;
  17.     long long c;
  18.  
  19.     bool operator==(const triangle& other) const {
  20.         if (a == other.a && other.b == b && c == other.c)
  21.             return true;
  22.         return false;
  23.     }
  24.  
  25.     bool operator!=(const triangle& other) const {
  26.         return !(*this == other);
  27.     }
  28. };
  29.  
  30.  
  31. long long mod(long long a, long long b) {
  32.     if (b < 0)
  33.         return mod(-a, -b);
  34.     long long ret = a % b;
  35.     if (ret < 0)
  36.         ret += b;
  37.     return ret;
  38. }
  39.  
  40. long long count_hash(triangle tr) {
  41.     const long long p = 4294967295;
  42.     const long long x = 877;
  43.     long long hash = 0;
  44.  
  45.     hash = mod(
  46.         mod(mod(tr.a * x, p) + mod(mod(tr.b * x, p)* x, p), p) +
  47.         mod(mod(mod(tr.c * x, p)* x, p)* x, p), p);
  48.     return hash;
  49. }
  50.  
  51. long long GCD(long long a, long long b) {
  52.     return b == 0 ? a : GCD(b, a % b);
  53. }
  54.  
  55. long long find_GCD(long long a, long long b, long long c) {
  56.     return GCD(GCD(a, b), c);
  57. }
  58.  
  59. triangle canonical(triangle tr) {
  60.     long long gcd = find_GCD(tr.a, tr.b, tr.c);
  61.     if (gcd > 1) {
  62.         tr.a /= gcd;
  63.         tr.b /= gcd;
  64.         tr.c /= gcd;
  65.     }
  66.     return tr;
  67. }
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76. class LinkedHashEntry {
  77. private:
  78.     triangle key;
  79.     int value;
  80.     LinkedHashEntry *next;
  81.  
  82. public:
  83.     LinkedHashEntry(triangle key, int value) {
  84.         this->key = key;
  85.         this->value = value;
  86.         this->next = NULL;
  87.     }
  88.  
  89.     triangle getKey() {
  90.         return key;
  91.     }
  92.  
  93.     LinkedHashEntry *getNext() {
  94.         return next;
  95.     }
  96.  
  97.     void setNext(LinkedHashEntry *next) {
  98.         this->next = next;
  99.     }
  100. };
  101.  
  102.  
  103.  
  104.  
  105.  
  106.  
  107.  
  108. class HashMap {
  109. private:
  110.     LinkedHashEntry **table;
  111.  
  112. public:
  113.     long long counter = 0;
  114.  
  115.     HashMap() {
  116.         table = new LinkedHashEntry*[TABLE_SIZE];
  117.         for (int i = 0; i < TABLE_SIZE; ++i)
  118.             table[i] = NULL;
  119.     }
  120.  
  121.  
  122.     void put(triangle key, int value) {
  123.         int hash = (count_hash(key) % TABLE_SIZE);
  124.         if (table[hash] == NULL) {
  125.             table[hash] = new LinkedHashEntry(key, value);
  126.             ++counter;
  127.         } else {
  128.             LinkedHashEntry *entry = table[hash];
  129.             while (entry->getNext() != NULL)// &&  entry->getKey != key)
  130.                 entry = entry->getNext();
  131.             if (entry->getKey() == key) {} // убрал getvalue
  132.             else
  133.             {
  134.                 entry->setNext(new LinkedHashEntry(key, value));
  135.                 ++counter;
  136.             }
  137.         }
  138.     }
  139.  
  140.  
  141.     ~HashMap() {
  142.         for (int i = 0; i < TABLE_SIZE; ++i)
  143.             if (table[i] != NULL) {
  144.                 LinkedHashEntry *prevEntry = NULL;
  145.                 LinkedHashEntry *entry = table[i];
  146.                 while (entry != NULL) {
  147.                     prevEntry = entry;
  148.                     entry = entry->getNext();
  149.                     delete prevEntry;
  150.                 }
  151.             }
  152.         delete[] table;
  153.     }
  154. };
  155.  
  156.  
  157.  
  158. int main() {
  159.     HashMap hashMap;
  160.     int n = 0;
  161.     int a[3];
  162.     long long num = 0;
  163.     std::ifstream input("input.txt");
  164.     std::ofstream output("output.txt");
  165.  
  166.     if (input.is_open())
  167.     {
  168.         input >> n;
  169.         for (int i = 0; i < n; ++i) {
  170.             input >> a[0];
  171.             input >> a[1];
  172.             input >> a[2];
  173.             std::sort(a, a + 3);
  174.             hashMap.put(canonical(triangle(a[0], a[1], a[2])), i);
  175.         }
  176.     }
  177.  
  178.     output << hashMap.counter;
  179.  
  180.     return 0;
  181. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement