Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef vector<int> vi;
- typedef vector<vi> vvi;
- struct Point {
- int x, y;
- Point(int a, int b) {
- x = a;
- y = b;
- }
- };
- typedef vector<Point> vp;
- istream &operator>> (istream &in, Point &P) {
- in >> P.x >> P.y;
- return in;
- }
- struct Vector {
- int x, y;
- Vector(int a, int b) {
- x = a;
- y = b;
- }
- Vector(const Point &A, const Point &B) {
- x = B.x - A.x;
- y = B.y - A.y;
- }
- int dist2() {
- return x*x + y*y;
- }
- };
- typedef vector<Vector> vv;
- typedef vector<vv> vvv;
- int operator* (const Vector &a, const Vector &b) {
- return a.x*b.x + a.y*b.y;
- }
- int operator^ (const Vector &a, const Vector &b) {
- return a.x*b.y - b.x*a.y;
- }
- int n=0, tn=0;
- vp points; // исходные точки в порядке ввода
- vvv vecs; // матрица с длинами
- vvi g; // граф
- vi p, color; // предки, цвета
- set<vi> cycle, box; // все циклы
- void add_cycle(int cycle_end, int cycle_st) {
- vi curr_cycle, sorted;
- curr_cycle.push_back(cycle_st);
- for (int v=cycle_end; v!=cycle_st; v=p[v])
- curr_cycle.push_back(v);
- sorted = curr_cycle; // создать копию без последнего элемента
- curr_cycle.push_back(cycle_st);
- sort (sorted.begin(), sorted.end());
- // неориентированный граф
- // избавляюсь от вырожденности (v - to - v)
- if (curr_cycle.size()>3 && count(box.begin(), box.end(), sorted)==0) {
- cycle.insert(curr_cycle);
- box.insert(sorted);
- }
- }
- void dfs(int v) {
- color[v] = 1;
- for (int to: g[v]) {
- if (color[to] == 0) {
- p[to] = v;
- dfs(to);
- } else if (color[to] == 1) {
- add_cycle(v, to);
- }
- }
- color[v] = 0;
- }
- void find_cycles() {
- for (int i=1; i<=n; i++)
- if (color[i] == 0)
- dfs(i);
- }
- int main() {
- cin >> n;
- points.assign(n, Point(0, 0));
- vecs.assign(n, vv(n, Vector(0, 0)));
- for (Point &p: points) cin >> p;
- // храню по длине количество ребер и точки
- map<int, pair<int, vector< pair<int, int> > > > lens;
- for (int i=0; i<n; i++) {
- for (int j=0; j<n; j++) {
- if (i == j) continue;
- vecs[i][j] = Vector(points[i], points[j]);
- vecs[j][i] = vecs[i][j];
- lens[vecs[i][j].dist2()].first++;
- lens[vecs[i][j].dist2()].second.push_back({i, j});
- }
- }
- for (auto spec: lens) {
- if (spec.second.first < 6) continue;
- tn = spec.second.second.size() * 2; // максимальное количество точек в новом графе
- g.assign(tn + 1, vi());
- p.assign(tn + 1, 0);
- color.assign(tn + 1, 0);
- for (auto arr: spec.second.second) {
- // тут нужно доделать (что бы не повторялись точки)
- int v=arr.first+1, u=arr.second+1;
- g[v].push_back(u);
- g[u].push_back(v);
- }
- cycle.clear();
- box.clear();
- find_cycles();
- for (auto cyc: cycle) {
- cout << '\n';
- cout << "[len: " << spec.first << "] ";
- for (auto v : cyc)
- cout << v << ' ';
- }
- }
- }
- /*
- 13
- 2 2
- 7 4
- 9 5
- 10 7
- 9 11
- 7 12
- 5 11
- 4 9
- 5 5
- 1 7
- 12 4
- 13 9
- 6 8
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement