Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <compare>
- #include <absl/time/time.h>
- #include <absl/time/clock.h>
- #include <sstream>
- #include <map>
- #include <regex>
- #include <absl/algorithm/container.h>
- #include <absl/strings/str_split.h>
- #include <absl/strings/str_cat.h>
- using namespace std;
- using M = array<array<int, 3>, 3>;
- struct Point {
- int x;
- int y;
- int z;
- auto operator<=>(const Point &) const = default;
- auto operator+(const Point &b) const {
- return Point{.x = x + b.x, .y = y + b.y, .z = z + b.z};
- }
- auto operator-(const Point &b) const {
- return Point{.x = x - b.x, .y = y - b.y, .z = z - b.z};
- }
- void operator+=(const Point &b) {
- x += b.x;
- y += b.y;
- z += b.z;
- }
- struct Hash {
- size_t operator()(const Point &p) const {
- size_t rowHash = std::hash<int>()(p.x);
- size_t colHash = std::hash<int>()(p.y) << 1;
- size_t zHash = std::hash<int>()(p.z) << 2;
- return rowHash ^ colHash ^ zHash;
- }
- };
- };
- Point Times(const M &m, const Point &p) {
- return Point{
- .x = m[0][0] * p.x + m[0][1] * p.y + m[0][2] * p.z,
- .y = m[1][0] * p.x + m[1][1] * p.y + m[1][2] * p.z,
- .z = m[2][0] * p.x + m[2][1] * p.y + m[2][2] * p.z
- };
- }
- M Times(const M &m, const M &p) {
- M ans;
- for (int i = 0; i < 3; ++i) {
- for (int j = 0; j < 3; ++j) {
- int x = 0;
- for (int k = 0; k < 3; ++k) {
- x += m[i][k] * p[k][j];
- }
- ans[i][j] = x;
- }
- }
- return ans;
- }
- array<M, 24> getAllPerms() {
- array<M, 24> ans;
- for (auto &a: ans) {
- for (auto &r: a) {
- for (auto &c: r) {
- c = 0;
- }
- }
- }
- int n = 0;
- for (int i = 0; i < 3; ++i) {
- for (int j = 0; j < 3; ++j) {
- if (i == j) continue;
- for (int mi = 1; mi >= -1; mi -= 2) {
- for (int mj = 1; mj >= -1; mj -= 2) {
- ans[n][i][0] = mi;
- ans[n][j][1] = mj;
- for (int k = 0; k < 3; ++k) {
- ans[n][k][2] = 1 * (ans[n][(k + 1) % 3][0] * ans[n][(k + 2) % 3][1] -
- ans[n][(k + 2) % 3][0] * ans[n][(k + 1) % 3][1]);
- }
- ++n;
- }
- }
- }
- }
- return ans;
- }
- int main() {
- auto start = absl::Now();
- auto allPerms = getAllPerms();
- vector<array<unordered_set<Point, Point::Hash>, 24>> scanners(1);
- string line;
- getline(cin, line);
- regex r(R"((-?\d+),(-?\d+),(-?\d+))");
- smatch base_match;
- for (; getline(cin, line);) {
- if (line.empty()) {
- scanners.emplace_back();
- // header.
- getline(cin, line);
- continue;
- }
- regex_match(line, base_match, r);
- auto p = Point{.x=stoi(base_match[1]),
- .y = stoi(base_match[2]),
- .z = stoi(base_match[3])};
- int i = 0;
- for (auto m: allPerms) {
- scanners.back()[i].insert(Times(m, p));
- ++i;
- }
- }
- unordered_set<Point, Point::Hash> m = scanners[0][0];
- map<pair<int, int>, pair<M, Point>> T;
- for (int i = 0; i < scanners.size(); ++i) {
- for (int j = 0; j < scanners.size(); ++j) {
- if (i == j) continue;
- bool found = false;
- for (int r = 0; r < 24; ++r) {
- if (found) break;
- for (const auto &pj: scanners[j][r]) {
- if (found) break;
- for (const auto &pi: scanners[i][0]) {
- if (found) break;
- auto d = pj - pi;
- int n_match = absl::c_count_if(scanners[j][r], [&scanners, i, &d](const Point &p) {
- return absl::c_any_of(scanners[i][0], [&p, &d](const Point &p2) {
- return (p - d) == p2;
- });
- });
- if (n_match >= 12) {
- T[make_pair(i, j)] = make_pair(allPerms[r], d);
- found = true;
- }
- }
- }
- }
- }
- }
- map<int, pair<M, Point>> abs;
- auto init = make_pair(M{{{{1, 0, 0}}, {{0, 1, 0}}, {{0, 0, 1}}}}, Point{.x = 0, .y = 0, .z = 0});
- vector<pair<int, pair<M, Point>>> to_visit{make_pair(0, init)};
- unordered_set<int> visited;
- while (!to_visit.empty()) {
- auto v = to_visit.back();
- to_visit.pop_back();
- if (visited.contains(v.first)) continue;
- visited.insert(v.first);
- abs.insert(v);
- for (auto t: T) {
- if (t.first.first == v.first) {
- pair<M, Point> composed = make_pair(Times(v.second.first, t.second.first),
- Times(v.second.first, t.second.second) + v.second.second);
- to_visit.push_back(make_pair(t.first.second, composed));
- }
- }
- }
- unordered_set<Point, Point::Hash> M;
- for (int i = 0; i< scanners.size(); ++i) {
- for (const auto& p: scanners[i][0]) {
- M.insert(Times(abs[i].first, p) - abs[i].second);
- }
- }
- int max_dist = 0;
- for (int i = 0; i< scanners.size(); ++i) {
- for (int j = 0; j< scanners.size(); ++j) {
- auto d = abs[j].second - abs[i].second;
- max_dist = max(max_dist, std::abs(d.x) + std::abs(d.y) + std::abs(d.z));
- }
- }
- cout << M.size() << endl;
- cout << max_dist << endl;
- cout << absl::Now() - start << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment