Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <deque>
- #include <random>
- #include <stdexcept>
- #include <fstream>
- #include <sstream>
- #include <unordered_map>
- #include <unordered_set>
- #include <numeric>
- using std::cin;
- using std::cout;
- using std::endl;
- using std::ofstream;
- using std::vector;
- inline int64_t Modulo(int64_t ii, int64_t nn)
- {
- return ((ii % nn) + nn) % nn;
- };
- struct Triangle
- {
- Triangle(int64_t aa, int64_t bb, int64_t cc, int64_t size) : aa_(aa), bb_(bb), cc_(cc), size_(size)
- {
- vector<int64_t> vals = {aa, bb, cc};
- int64_t gcd = std::gcd(std::gcd(aa, bb), cc);
- std::sort(vals.begin(), vals.end());
- aa_ = vals[0] / gcd;
- bb_ = vals[1] / gcd;
- cc_ = vals[2] / gcd;
- hash_ = CalculatePolyHash_();
- };
- bool operator*(Triangle &other)
- {
- return ((aa_ == other.aa_) && (bb_ == other.bb_) && (cc_ == other.cc_));
- };
- int64_t hash_;
- private:
- // std::size_t CalculatePolyHash_()
- // {
- // std::size_t first = std::hash<unsigned long long>{}(aa_);
- // std::size_t second = std::hash<unsigned long long>{}(bb_);
- // std::size_t third = std::hash<unsigned long long>{}(cc_);
- // return first ^ (second << 1) ^ (third << 3);
- // };
- int64_t CalculatePolyHash_()
- {
- vector<int64_t> vector = {aa_, bb_, cc_};
- int64_t pp = std::pow(10, 9) + 7;
- int64_t length = 3;
- int64_t hash = 0;
- for (int64_t i = 0; i < length; ++i)
- {
- int64_t el = vector[i];
- int64_t val = std::pow(el * pp, length - (i + 1));
- hash += val;
- }
- return Modulo(hash, size_);
- };
- int64_t size_;
- int64_t aa_;
- int64_t bb_;
- int64_t cc_;
- };
- class FixedSet
- {
- public:
- FixedSet() = default;
- void InsertTriangle(Triangle &triangle);
- int64_t GetHashMapSize();
- void InitVector();
- int64_t size_ = 1'000'000 / 1000;
- private:
- vector<vector<Triangle>> hash_map_{};
- int64_t hashMapSize_ = 0;
- };
- int64_t FixedSet::GetHashMapSize()
- {
- return hashMapSize_;
- };
- void FixedSet::InitVector()
- {
- for (int i = 0; i < size_; ++i)
- {
- hash_map_.push_back({});
- }
- }
- //
- void FixedSet::InsertTriangle(Triangle &triangle)
- {
- int idx = triangle.hash_;
- for (Triangle cur_trinagle : hash_map_[idx])
- {
- if (cur_trinagle * triangle)
- {
- return;
- }
- }
- hash_map_[idx].push_back(triangle);
- ++hashMapSize_;
- };
- int main()
- {
- int64_t nn;
- cin >> nn;
- FixedSet fixedSet;
- fixedSet.InitVector();
- while (nn--)
- {
- int64_t aa, bb, cc;
- cin >> aa;
- cin >> bb;
- cin >> cc;
- Triangle tri(aa, bb, cc, fixedSet.size_);
- fixedSet.InsertTriangle(tri);
- }
- cout << fixedSet.GetHashMapSize() << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement