Advertisement
ivnikkk

Untitled

Dec 27th, 2022
831
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.34 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include "bits/stdc++.h"
  3. using namespace std;
  4. #define all(a) a.begin(), a.end()
  5. #define Vec Point
  6. typedef long double ld;
  7. mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
  8.  
  9. const ld Pi = 3.14159265358979323846;
  10. const ld eps = 1e-13;
  11.  
  12. int sign(ld x) {
  13.     if(x > eps) { return 1; }
  14.     if(x < -eps) { return -1; }
  15.     return 0;
  16. }
  17. ld sq(ld x) {
  18.     return x * x;
  19. }
  20. struct Point {
  21.     ld x, y;
  22.     Point() : x(0), y(0) {}
  23.     Point(ld _x, ld _y) : x(_x), y(_y) {}
  24.     ld len2() {
  25.         return sq(x) + sq(y);
  26.     }
  27.     ld operator^(const Point& other) {
  28.          return x * other.y - y * other.x;
  29.     }
  30.     ld operator*(const Point& other) {
  31.         return x * other.x + y * other.y;
  32.     }
  33.     Point operator-(const Point & other) {
  34.         return Point(x - other.x, y - other.y);
  35.     }
  36. };
  37.  
  38. istream& operator >> (istream& in, Point& val) {
  39.     return in >> val.x >> val.y;
  40. }
  41. struct Triangle {
  42.     int k = 0, ind = -1;
  43.     Point a[3] = {};
  44.     ld angle[3] = {-1, -1, -1};
  45.     ld len[3] = {-1, -1, -1};
  46.     void read(int _ind) {
  47.         ind = _ind;
  48.         for (int i = 0; i < 3; i++) {
  49.             cin >> a[i];
  50.         }
  51.     }
  52.     ld get_angle0() {
  53.         if(sign(angle[k] + 1.00) == 0) {
  54.             Vec ab = a[(k + 1) % 3] - a[(k + 0) % 3];
  55.             Vec ac = a[(k + 2) % 3] - a[(k + 0) % 3];
  56.             return angle[k] = fabs(atan2((ab ^ ac), (ab * ac)));
  57.         }
  58.         return angle[k];
  59.     }
  60.     ld get_angle1() {
  61.         if (sign(angle[(k + 1) % 3] + 1.00) == 0) {
  62.             Vec ba = a[(k + 0) % 3] - a[(k + 1) % 3];
  63.             Vec bc = a[(k + 2) % 3] - a[(k + 1) % 3];
  64.             return angle[(k + 1) % 3 ] = fabs(atan2((bc ^ ba), (bc * ba)));
  65.         }
  66.         return angle[(k + 1) % 3];
  67.     }
  68.     ld get_angle2() {
  69.         if (sign(angle[(k + 2) % 3] + 1.00) == 0) {
  70.             Vec ca = a[(k + 0) % 3] - a[(k + 2) % 3];
  71.             Vec cb = a[(k + 1) % 3] - a[(k + 2) % 3];
  72.             return fabs(atan2((cb ^ ca), (cb * ca)));
  73.         }
  74.         return angle[(k + 2) % 3];
  75.     }
  76.     ld get_seg01() {
  77.         if(len[0] == -1) {
  78.             Vec ab = a[(k + 1) % 3] - a[(k + 0) % 3];
  79.             return len[0] = ab.len2();
  80.         }
  81.         return len[0];
  82.     }
  83.     ld get_seg12() {
  84.         if(len[1] == -1) {
  85.             Vec bc = a[(k + 2) % 3] - a[(k + 1) % 3];
  86.             return len[1] = bc.len2();
  87.         }
  88.         return len[1];
  89.     }
  90.     ld get_seg02() {
  91.         if(len[2] == -1) {
  92.             Vec ac = a[(k + 0) % 3] - a[(k + 2) % 3];
  93.             return len[2] = ac.len2();
  94.         }
  95.         return len[2];
  96.     }
  97. };
  98. const long long mod = 1e9 + 7;
  99.  
  100. signed main() {
  101. #ifdef _DEBUG
  102.     freopen("input.txt", "r", stdin);
  103.     freopen("output.txt", "w", stdout);
  104. #endif
  105.     ios_base::sync_with_stdio(false);
  106.     cin.tie(nullptr);
  107.     int t; cin >> t;
  108.     int n; cin >> n;
  109.     vector<Triangle> arr;
  110.     vector<long long> rnd_hsh(n);
  111.     for (int i = 0; i < n; i++) {
  112.         rnd_hsh[i] = rnd();
  113.         Triangle x; x.read(i);
  114.         Triangle x2 = x; x2.k = 1;
  115.         Triangle x3 = x; x3.k = 2;
  116.         arr.push_back(x);
  117.         arr.push_back(x2);
  118.         arr.push_back(x3);
  119.     }
  120.     vector<vector<int>> ans;
  121.     auto count_hash = [&](vector<int>& a) {
  122.         long long hsh = 0;
  123.         for (int i = 0; i < (int)a.size(); i++) {
  124.             hsh += rnd_hsh[a[i] - 1];
  125.             hsh %= mod;
  126.         }
  127.         return hsh;
  128.     };
  129.     auto check_angle = [&](ld x) {
  130.         return sign(x - Pi) == 0;
  131.     };
  132.     n = (int)arr.size();
  133.     unordered_set<long long> used(n * n * n * 2);
  134.     for (int a = 0; a < n; a++) {
  135.         for (int b = 0; b < n; b++) {
  136.             if(arr[a].ind == arr[b].ind) { continue; }
  137.             for (int c = 0; c < n; c++) {
  138.                 if (arr[b].ind == arr[c].ind || arr[c].ind == arr[a].ind) { continue; }
  139.                 for (int d = 0; d < n; d++) {
  140.                     if(arr[c].ind == arr[d].ind || arr[d].ind == arr[a].ind || arr[d].ind == arr[b].ind) { continue; }
  141.                     Triangle& A = arr[a];
  142.                     Triangle& B = arr[b];
  143.                     Triangle& C = arr[c];
  144.                     Triangle& D = arr[d];
  145.                     if (sign(A.get_seg12() - B.get_seg01()) == 0 &&
  146.                         sign(B.get_seg02() - D.get_seg01()) == 0 &&
  147.                         sign(C.get_seg02() - B.get_seg12()) == 0 &&
  148.                         check_angle(A.get_angle2() + B.get_angle0() + D.get_angle0()) &&
  149.                         check_angle(A.get_angle1() + B.get_angle1() + C.get_angle0()) &&
  150.                         check_angle(C.get_angle2() + B.get_angle2() + D.get_angle1())
  151.                         ) {
  152.                         vector<int> psh = vector<int> { arr[a].ind + 1, arr[b].ind + 1, arr[c].ind + 1, arr[d].ind + 1 };
  153.                         long long hs = count_hash(psh);
  154.                         if(used.find(hs) == used.end()) {
  155.                             ans.push_back(psh);
  156.                             used.insert(hs);
  157.                         }
  158.                     }
  159.                 }
  160.             }
  161.         }
  162.     }
  163.     cout << (int)ans.size() << '\n';
  164.     for (auto& it : ans) {
  165.         vector<int> pr = it;
  166.         for (int& i : pr) {
  167.             cout << i << ' ';
  168.         }
  169.         cout << '\n';
  170.     }
  171. }
  172.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement