Advertisement
elkcl

C1 2022 геома

Jan 19th, 2022
758
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #ifndef ONPC
  2. #pragma GCC optimize("O3")
  3. #pragma GCC target("avx,avx2,sse,sse2,sse3,ssse3,sse4.1,sse4.2,lzcnt,bmi")
  4. //pragma GCC optimize("unroll-loops")
  5. #endif
  6.  
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <vector>
  10. #include <cmath>
  11. #include <utility>
  12. #include <algorithm>
  13. #include <numeric>
  14. #include <array>
  15. #include <set>
  16. #include <unordered_set>
  17.  
  18. using namespace std;
  19. using ll = int64_t;
  20. using ld = long double;
  21. using ii = pair<int, int>;
  22. using vi = vector<int>;
  23. using vvi = vector<vi>;
  24. using vii = vector<ii>;
  25.  
  26. #define all(x) (x).begin(), (x).end()
  27.  
  28. const ld PI = acos(-1);
  29. const ld EPS = 1e-11;
  30.  
  31. struct pt {
  32.     int x, y;
  33.  
  34.     ll abs2() const {
  35.         return 1ll * x * x + 1ll * y * y;
  36.     }
  37. };
  38.  
  39. inline pt operator+(pt a, pt b) {
  40.     return {a.x + b.x, a.y + b.y};
  41. }
  42.  
  43. inline pt operator-(pt a) {
  44.     return {-a.x, -a.y};
  45. }
  46.  
  47. inline pt operator-(pt a, pt b) {
  48.     return a + (-b);
  49. }
  50.  
  51. inline pt operator*(pt a, int k) {
  52.     return {a.x * k, a.y * k};
  53. }
  54.  
  55. inline pt operator*(int k, pt a) {
  56.     return {a.x * k, a.y * k};
  57. }
  58.  
  59. inline ll operator*(pt a, pt b) {
  60.     return 1ll * a.x * b.x + 1ll * a.y * b.y;
  61. }
  62.  
  63. inline ll operator%(pt a, pt b) {
  64.     return 1ll * a.x * b.y - 1ll * a.y * b.x;
  65. }
  66.  
  67. inline ld operator^(pt a, pt b) {
  68.     return atan2(a % b, a * b);
  69. }
  70.  
  71. struct tri {
  72.     pt a, b, c;
  73.  
  74.     pt s(int o) const {
  75.         if (o == 0)
  76.             return b - a;
  77.         else if (o == 1)
  78.             return c - b;
  79.         else
  80.             return a - c;
  81.     }
  82.  
  83.     ld ang(int o) const {
  84.         if (o == 0)
  85.             return (b - a) ^ (c - a);
  86.         else if (o == 1)
  87.             return (c - b) ^ (a - b);
  88.         else
  89.             return (a - c) ^ (b - c);
  90.     }
  91. };
  92.  
  93. int32_t main() {
  94.     ios_base::sync_with_stdio(false);
  95.     cin.tie(nullptr);
  96.     cout.tie(nullptr);
  97.  
  98.     int t, n;
  99.     cin >> t >> n;
  100.     vector<tri> a(n);
  101.     for (auto &e : a)
  102.         cin >> e.a.x >> e.a.y >> e.b.x >> e.b.y >> e.c.x >> e.c.y;
  103.     set<tuple<int, int, int, int>> ans;
  104.  
  105.     for (int c = 0; c < n; ++c) {
  106.         auto& cent = a[c];
  107.         for (int i0 = 0; i0 < n; ++i0) {
  108.             if (i0 == c)
  109.                 continue;
  110.             auto& t0 = a[i0];
  111.             for (int o0 = 0; o0 < 3; ++o0) {
  112.                 if (cent.s(0).abs2() != t0.s(o0).abs2())
  113.                     continue;
  114.                 for (int i1 = 0; i1 < n; ++i1) {
  115.                     if (i1 == c || i1 == i0)
  116.                         continue;
  117.                     auto& t1 = a[i1];
  118.                     for (int o1 = 0; o1 < 3; ++o1) {
  119.                         if (cent.s(1).abs2() != t1.s(o1).abs2())
  120.                             continue;
  121.                         if (abs(cent.ang(1) + t0.ang(o0) + t1.ang((o1 + 1) % 3) - PI) > EPS)
  122.                             continue;
  123.                         for (int i2 = 0; i2 < n; ++i2) {
  124.                             if (i2 == c || i2 == i0 || i2 == i1)
  125.                                 continue;
  126.                             auto& t2 = a[i2];
  127.                             for (int o2 = 0; o2 < 3; ++o2) {
  128.                                 if (cent.s(2).abs2() != t2.s(o2).abs2())
  129.                                     continue;
  130.                                 if (abs(cent.ang(0) + t0.ang((o0 + 1) % 3) + t2.ang(o2) - PI) > EPS)
  131.                                     continue;
  132.                                 if (abs(cent.ang(2) + t1.ang(o1) + t2.ang((o2 + 1) % 3) - PI) > EPS)
  133.                                     continue;
  134.                                 array<int, 4> comb{c, i0, i1, i2};
  135.                                 sort(all(comb));
  136.                                 ans.insert({comb[0], comb[1], comb[2], comb[3]});
  137.                             }
  138.                         }
  139.                     }
  140.                 }
  141.             }
  142.         }
  143.     }
  144.  
  145.     cout << ans.size() << '\n';
  146.     for (auto &comb : ans) {
  147.         auto [a1, a2, a3, a4] = comb;
  148.         cout << a1 + 1 << ' ' << a2 + 1 << ' ' << a3 + 1 << ' ' << a4 + 1 << '\n';
  149.     }
  150. }
Advertisement
Advertisement
Advertisement
RAW Paste Data Copied
Advertisement