ErnestGalbrun

Untitled

Dec 26th, 2021
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 5.88 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <compare>
  5. #include <absl/time/time.h>
  6. #include <absl/time/clock.h>
  7. #include <sstream>
  8. #include <map>
  9. #include <regex>
  10. #include <absl/algorithm/container.h>
  11. #include <absl/strings/str_split.h>
  12. #include <absl/strings/str_cat.h>
  13.  
  14. using namespace std;
  15.  
  16. using M = array<array<int, 3>, 3>;
  17.  
  18. struct Point {
  19.     int x;
  20.     int y;
  21.     int z;
  22.  
  23.     auto operator<=>(const Point &) const = default;
  24.  
  25.     auto operator+(const Point &b) const {
  26.         return Point{.x = x + b.x, .y = y + b.y, .z = z + b.z};
  27.     }
  28.  
  29.     auto operator-(const Point &b) const {
  30.         return Point{.x = x - b.x, .y = y - b.y, .z = z - b.z};
  31.     }
  32.  
  33.     void operator+=(const Point &b) {
  34.         x += b.x;
  35.         y += b.y;
  36.         z += b.z;
  37.     }
  38.  
  39.     struct Hash {
  40.         size_t operator()(const Point &p) const {
  41.             size_t rowHash = std::hash<int>()(p.x);
  42.             size_t colHash = std::hash<int>()(p.y) << 1;
  43.             size_t zHash = std::hash<int>()(p.z) << 2;
  44.             return rowHash ^ colHash ^ zHash;
  45.         }
  46.     };
  47. };
  48.  
  49. Point Times(const M &m, const Point &p) {
  50.     return Point{
  51.             .x = m[0][0] * p.x + m[0][1] * p.y + m[0][2] * p.z,
  52.             .y = m[1][0] * p.x + m[1][1] * p.y + m[1][2] * p.z,
  53.             .z = m[2][0] * p.x + m[2][1] * p.y + m[2][2] * p.z
  54.     };
  55. }
  56.  
  57. M Times(const M &m, const M &p) {
  58.     M ans;
  59.     for (int i = 0; i < 3; ++i) {
  60.         for (int j = 0; j < 3; ++j) {
  61.             int x = 0;
  62.             for (int k = 0; k < 3; ++k) {
  63.                 x += m[i][k] * p[k][j];
  64.             }
  65.             ans[i][j] = x;
  66.         }
  67.     }
  68.     return ans;
  69. }
  70.  
  71. array<M, 24> getAllPerms() {
  72.     array<M, 24> ans;
  73.     for (auto &a: ans) {
  74.         for (auto &r: a) {
  75.             for (auto &c: r) {
  76.                 c = 0;
  77.             }
  78.         }
  79.     }
  80.     int n = 0;
  81.     for (int i = 0; i < 3; ++i) {
  82.         for (int j = 0; j < 3; ++j) {
  83.             if (i == j) continue;
  84.             for (int mi = 1; mi >= -1; mi -= 2) {
  85.                 for (int mj = 1; mj >= -1; mj -= 2) {
  86.                     ans[n][i][0] = mi;
  87.                     ans[n][j][1] = mj;
  88.                     for (int k = 0; k < 3; ++k) {
  89.                         ans[n][k][2] = 1 * (ans[n][(k + 1) % 3][0] * ans[n][(k + 2) % 3][1] -
  90.                                              ans[n][(k + 2) % 3][0] * ans[n][(k + 1) % 3][1]);
  91.                     }
  92.                     ++n;
  93.                 }
  94.             }
  95.         }
  96.     }
  97.     return ans;
  98. }
  99.  
  100. int main() {
  101.     auto start = absl::Now();
  102.     auto allPerms = getAllPerms();
  103.  
  104.     vector<array<unordered_set<Point, Point::Hash>, 24>> scanners(1);
  105.     string line;
  106.     getline(cin, line);
  107.     regex r(R"((-?\d+),(-?\d+),(-?\d+))");
  108.     smatch base_match;
  109.     for (; getline(cin, line);) {
  110.         if (line.empty()) {
  111.             scanners.emplace_back();
  112.             // header.
  113.             getline(cin, line);
  114.             continue;
  115.         }
  116.  
  117.         regex_match(line, base_match, r);
  118.         auto p = Point{.x=stoi(base_match[1]),
  119.                 .y = stoi(base_match[2]),
  120.                 .z = stoi(base_match[3])};
  121.         int i = 0;
  122.         for (auto m: allPerms) {
  123.             scanners.back()[i].insert(Times(m, p));
  124.             ++i;
  125.         }
  126.     }
  127.     unordered_set<Point, Point::Hash> m = scanners[0][0];
  128.     map<pair<int, int>, pair<M, Point>> T;
  129.     for (int i = 0; i < scanners.size(); ++i) {
  130.         for (int j = 0; j < scanners.size(); ++j) {
  131.             if (i == j) continue;
  132.             bool found = false;
  133.             for (int r = 0; r < 24; ++r) {
  134.                 if (found) break;
  135.                 for (const auto &pj: scanners[j][r]) {
  136.                     if (found) break;
  137.                     for (const auto &pi: scanners[i][0]) {
  138.                         if (found) break;
  139.                         auto d = pj - pi;
  140.                         int n_match = absl::c_count_if(scanners[j][r], [&scanners, i, &d](const Point &p) {
  141.                             return absl::c_any_of(scanners[i][0], [&p, &d](const Point &p2) {
  142.                                 return (p - d) == p2;
  143.                             });
  144.                         });
  145.  
  146.                         if (n_match >= 12) {
  147.                             T[make_pair(i, j)] = make_pair(allPerms[r], d);
  148.                             found = true;
  149.                         }
  150.                     }
  151.                 }
  152.             }
  153.         }
  154.     }
  155.  
  156.     map<int, pair<M, Point>> abs;
  157.     auto init = make_pair(M{{{{1, 0, 0}}, {{0, 1, 0}}, {{0, 0, 1}}}}, Point{.x = 0, .y = 0, .z = 0});
  158.     vector<pair<int, pair<M, Point>>> to_visit{make_pair(0, init)};
  159.     unordered_set<int> visited;
  160.     while (!to_visit.empty()) {
  161.         auto v = to_visit.back();
  162.         to_visit.pop_back();
  163.         if (visited.contains(v.first)) continue;
  164.         visited.insert(v.first);
  165.         abs.insert(v);
  166.         for (auto t: T) {
  167.             if (t.first.first == v.first) {
  168.                 pair<M, Point> composed = make_pair(Times(v.second.first, t.second.first),
  169.                                                     Times(v.second.first, t.second.second) + v.second.second);
  170.                 to_visit.push_back(make_pair(t.first.second, composed));
  171.             }
  172.         }
  173.     }
  174.  
  175.     unordered_set<Point, Point::Hash> M;
  176.     for (int i = 0; i< scanners.size(); ++i) {
  177.         for (const auto& p: scanners[i][0]) {
  178.             M.insert(Times(abs[i].first, p) - abs[i].second);
  179.         }
  180.     }
  181.     int max_dist = 0;
  182.     for (int i = 0; i< scanners.size(); ++i) {
  183.             for (int j = 0; j< scanners.size(); ++j) {
  184.                 auto d = abs[j].second - abs[i].second;
  185.                 max_dist = max(max_dist, std::abs(d.x) + std::abs(d.y) + std::abs(d.z));
  186.             }
  187.     }
  188.  
  189.  
  190.  
  191.     cout << M.size() << endl;
  192.     cout << max_dist << endl;
  193.     cout << absl::Now() - start << endl;
  194.  
  195.     return 0;
  196. }
  197.  
Advertisement
Add Comment
Please, Sign In to add comment