Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #define _CRT_SECURE_NO_WARNINGS
- #include "bits/stdc++.h"
- using namespace std;
- #define all(a) a.begin(), a.end()
- #define Vec Point
- typedef long double ld;
- mt19937 rnd(std::chrono::high_resolution_clock::now().time_since_epoch().count());
- const ld Pi = 3.14159265358979323846;
- const ld eps = 1e-13;
- int sign(ld x) {
- if(x > eps) { return 1; }
- if(x < -eps) { return -1; }
- return 0;
- }
- ld sq(ld x) {
- return x * x;
- }
- struct Point {
- ld x, y;
- Point() : x(0), y(0) {}
- Point(ld _x, ld _y) : x(_x), y(_y) {}
- ld len2() {
- return sq(x) + sq(y);
- }
- ld operator^(const Point& other) {
- return x * other.y - y * other.x;
- }
- ld operator*(const Point& other) {
- return x * other.x + y * other.y;
- }
- Point operator-(const Point & other) {
- return Point(x - other.x, y - other.y);
- }
- };
- istream& operator >> (istream& in, Point& val) {
- return in >> val.x >> val.y;
- }
- struct Triangle {
- int k = 0, ind = -1;
- Point a[3] = {};
- ld angle[3] = {-1, -1, -1};
- ld len[3] = {-1, -1, -1};
- void read(int _ind) {
- ind = _ind;
- for (int i = 0; i < 3; i++) {
- cin >> a[i];
- }
- }
- ld get_angle0() {
- if(sign(angle[k] + 1.00) == 0) {
- Vec ab = a[(k + 1) % 3] - a[(k + 0) % 3];
- Vec ac = a[(k + 2) % 3] - a[(k + 0) % 3];
- return angle[k] = fabs(atan2((ab ^ ac), (ab * ac)));
- }
- return angle[k];
- }
- ld get_angle1() {
- if (sign(angle[(k + 1) % 3] + 1.00) == 0) {
- Vec ba = a[(k + 0) % 3] - a[(k + 1) % 3];
- Vec bc = a[(k + 2) % 3] - a[(k + 1) % 3];
- return angle[(k + 1) % 3 ] = fabs(atan2((bc ^ ba), (bc * ba)));
- }
- return angle[(k + 1) % 3];
- }
- ld get_angle2() {
- if (sign(angle[(k + 2) % 3] + 1.00) == 0) {
- Vec ca = a[(k + 0) % 3] - a[(k + 2) % 3];
- Vec cb = a[(k + 1) % 3] - a[(k + 2) % 3];
- return fabs(atan2((cb ^ ca), (cb * ca)));
- }
- return angle[(k + 2) % 3];
- }
- ld get_seg01() {
- if(len[0] == -1) {
- Vec ab = a[(k + 1) % 3] - a[(k + 0) % 3];
- return len[0] = ab.len2();
- }
- return len[0];
- }
- ld get_seg12() {
- if(len[1] == -1) {
- Vec bc = a[(k + 2) % 3] - a[(k + 1) % 3];
- return len[1] = bc.len2();
- }
- return len[1];
- }
- ld get_seg02() {
- if(len[2] == -1) {
- Vec ac = a[(k + 0) % 3] - a[(k + 2) % 3];
- return len[2] = ac.len2();
- }
- return len[2];
- }
- };
- const long long mod = 1e9 + 7;
- signed main() {
- #ifdef _DEBUG
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- #endif
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- int t; cin >> t;
- int n; cin >> n;
- vector<Triangle> arr;
- vector<long long> rnd_hsh(n);
- for (int i = 0; i < n; i++) {
- rnd_hsh[i] = rnd();
- Triangle x; x.read(i);
- Triangle x2 = x; x2.k = 1;
- Triangle x3 = x; x3.k = 2;
- arr.push_back(x);
- arr.push_back(x2);
- arr.push_back(x3);
- }
- vector<vector<int>> ans;
- auto count_hash = [&](vector<int>& a) {
- long long hsh = 0;
- for (int i = 0; i < (int)a.size(); i++) {
- hsh += rnd_hsh[a[i] - 1];
- hsh %= mod;
- }
- return hsh;
- };
- auto check_angle = [&](ld x) {
- return sign(x - Pi) == 0;
- };
- n = (int)arr.size();
- unordered_set<long long> used(n * n * n * 2);
- for (int a = 0; a < n; a++) {
- for (int b = 0; b < n; b++) {
- if(arr[a].ind == arr[b].ind) { continue; }
- for (int c = 0; c < n; c++) {
- if (arr[b].ind == arr[c].ind || arr[c].ind == arr[a].ind) { continue; }
- for (int d = 0; d < n; d++) {
- if(arr[c].ind == arr[d].ind || arr[d].ind == arr[a].ind || arr[d].ind == arr[b].ind) { continue; }
- Triangle& A = arr[a];
- Triangle& B = arr[b];
- Triangle& C = arr[c];
- Triangle& D = arr[d];
- if (sign(A.get_seg12() - B.get_seg01()) == 0 &&
- sign(B.get_seg02() - D.get_seg01()) == 0 &&
- sign(C.get_seg02() - B.get_seg12()) == 0 &&
- check_angle(A.get_angle2() + B.get_angle0() + D.get_angle0()) &&
- check_angle(A.get_angle1() + B.get_angle1() + C.get_angle0()) &&
- check_angle(C.get_angle2() + B.get_angle2() + D.get_angle1())
- ) {
- vector<int> psh = vector<int> { arr[a].ind + 1, arr[b].ind + 1, arr[c].ind + 1, arr[d].ind + 1 };
- long long hs = count_hash(psh);
- if(used.find(hs) == used.end()) {
- ans.push_back(psh);
- used.insert(hs);
- }
- }
- }
- }
- }
- }
- cout << (int)ans.size() << '\n';
- for (auto& it : ans) {
- vector<int> pr = it;
- for (int& i : pr) {
- cout << i << ' ';
- }
- cout << '\n';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement