Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2019
114
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.52 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <list>
  5. #include <string>
  6. #include <utility>
  7.  
  8. struct Triangle {
  9.     int first, second, third;
  10.  
  11.     void setData(int a_val, int b_val, int c_val) {
  12.         std::vector<int> data = {a_val, b_val, c_val};
  13.         std::sort(data.begin(), data.end());
  14.         int gc = gcd(data[0], gcd(data[1], data[2]));
  15.         for (auto& edge : data) {
  16.             edge /= gc;
  17.         }
  18.         first = data[0];
  19.         second = data[1];
  20.         third = data[2];
  21.     }
  22.  
  23.     int gcd(int a_val, int b_val) {
  24.         if (b_val == 0) {
  25.             return a_val;    
  26.         }
  27.         return gcd(b_val, a_val % b_val);
  28.     }
  29. };
  30.  
  31. std::vector<Triangle> readTriangles() {
  32.     int size;
  33.     std::cin >> size;
  34.     std::vector<Triangle> data(size);
  35.     for (auto& tri : data) {
  36.         int a_val, b_val, c_val;
  37.         std::cin >> a_val >> b_val >> c_val;
  38.         tri.setData(a_val, b_val, c_val);
  39.     }
  40.     return data;
  41. }
  42.  
  43. int firstHash(const Triangle& tr) {
  44.     const int p_val = 1e9 + 7;
  45.     const int64_t q_val = 113;
  46.     const int m_val = 1e5;
  47.     return (tr.first*q_val*q_val + tr.second*q_val + tr.third) % p_val % m_val;
  48. }
  49.  
  50. int secondHash(const Triangle& tr) {
  51.     const int p_val = 1e9 + 9;
  52.     const int m_val = 1e5;
  53.     const int64_t q_val = 137;
  54.     return (tr.first*q_val*q_val + tr.second*q_val + tr.third) % p_val % m_val;
  55. }
  56.  
  57. int thirdHash(const Triangle& tr) {
  58.     const int p_val = 999999937;
  59.     const int m_val = 1e5;
  60.     const int64_t q_val = 171;
  61.     return (tr.first*q_val*q_val + tr.second*q_val + tr.third) % p_val % m_val;
  62. }
  63.  
  64. int solve(const std::vector<Triangle>& data) {
  65.     std::vector<std::list<std::pair<int, int>>> hash(100001); // hash, val
  66.     for (auto tr : data) {
  67.         auto& list = hash[firstHash(tr)];
  68.         int second = secondHash(tr);
  69.         int third = thirdHash(tr);
  70.         bool find = false;
  71.         for (auto it = list.begin(); it != list.end(); ++it) {
  72.             if (it->first == second && it->second == third) {
  73.                 find = true;
  74.                 break;
  75.             }
  76.         }
  77.         if (!find) {
  78.             list.push_back({second, third});
  79.         }
  80.     }
  81.  
  82.     int ans = 0;
  83.     for (auto i : hash) {
  84.         ans += i.size();
  85.     }
  86.     return ans;
  87. }
  88.  
  89. // #define TEST
  90. int main() {
  91.     std::ios_base::sync_with_stdio(false);
  92.     std::cin.tie(nullptr);
  93.  
  94. #ifdef TEST
  95.     return 0;
  96. #endif
  97.  
  98.     auto data = readTriangles();
  99.     int ans = solve(data);
  100.     std::cout << ans << '\n';
  101. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement