Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <vector>
- #include <list>
- #include <string>
- #include <utility>
- struct Triangle {
- int first, second, third;
- void setData(int a_val, int b_val, int c_val) {
- std::vector<int> data = {a_val, b_val, c_val};
- std::sort(data.begin(), data.end());
- int gc = gcd(data[0], gcd(data[1], data[2]));
- for (auto& edge : data) {
- edge /= gc;
- }
- first = data[0];
- second = data[1];
- third = data[2];
- }
- int gcd(int a_val, int b_val) {
- if (b_val == 0) {
- return a_val;
- }
- return gcd(b_val, a_val % b_val);
- }
- };
- std::vector<Triangle> readTriangles() {
- int size;
- std::cin >> size;
- std::vector<Triangle> data(size);
- for (auto& tri : data) {
- int a_val, b_val, c_val;
- std::cin >> a_val >> b_val >> c_val;
- tri.setData(a_val, b_val, c_val);
- }
- return data;
- }
- int firstHash(const Triangle& tr) {
- const int p_val = 1e9 + 7;
- const int64_t q_val = 113;
- const int m_val = 1e5;
- return (tr.first*q_val*q_val + tr.second*q_val + tr.third) % p_val % m_val;
- }
- int secondHash(const Triangle& tr) {
- const int p_val = 1e9 + 9;
- const int m_val = 1e5;
- const int64_t q_val = 137;
- return (tr.first*q_val*q_val + tr.second*q_val + tr.third) % p_val % m_val;
- }
- int thirdHash(const Triangle& tr) {
- const int p_val = 999999937;
- const int m_val = 1e5;
- const int64_t q_val = 171;
- return (tr.first*q_val*q_val + tr.second*q_val + tr.third) % p_val % m_val;
- }
- int solve(const std::vector<Triangle>& data) {
- std::vector<std::list<std::pair<int, int>>> hash(100001); // hash, val
- for (auto tr : data) {
- auto& list = hash[firstHash(tr)];
- int second = secondHash(tr);
- int third = thirdHash(tr);
- bool find = false;
- for (auto it = list.begin(); it != list.end(); ++it) {
- if (it->first == second && it->second == third) {
- find = true;
- break;
- }
- }
- if (!find) {
- list.push_back({second, third});
- }
- }
- int ans = 0;
- for (auto i : hash) {
- ans += i.size();
- }
- return ans;
- }
- // #define TEST
- int main() {
- std::ios_base::sync_with_stdio(false);
- std::cin.tie(nullptr);
- #ifdef TEST
- return 0;
- #endif
- auto data = readTriangles();
- int ans = solve(data);
- std::cout << ans << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement