Advertisement
Guest User

Untitled

a guest
Apr 20th, 2019
94
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.56 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. typedef vector<int> vi;
  6. typedef vector<vi> vvi;
  7.  
  8. struct Point {
  9.     int x, y;
  10.  
  11.     Point(int a, int b) {
  12.         x = a;
  13.         y = b;
  14.     }
  15. };
  16. typedef vector<Point> vp;
  17.  
  18. istream &operator>> (istream &in, Point &P) {
  19.     in >> P.x >> P.y;
  20.     return in;
  21. }
  22.  
  23. struct Vector {
  24.     int x, y;
  25.  
  26.     Vector(int a, int b) {
  27.         x = a;
  28.         y = b;
  29.     }
  30.  
  31.     Vector(const Point &A, const Point &B) {
  32.         x = B.x - A.x;
  33.         y = B.y - A.y;
  34.     }
  35.  
  36.     int dist2() {
  37.         return x*x + y*y;
  38.     }
  39. };
  40. typedef vector<Vector> vv;
  41. typedef vector<vv> vvv;
  42.  
  43. int operator* (const Vector &a, const Vector &b) {
  44.     return a.x*b.x + a.y*b.y;
  45. }
  46.  
  47. int operator^ (const Vector &a, const Vector &b) {
  48.     return a.x*b.y - b.x*a.y;
  49. }
  50.  
  51. int n=0, tn=0;
  52. vp points; // исходные точки в порядке ввода
  53. vvv vecs; // матрица с длинами
  54.  
  55. vvi g; // граф
  56. vi p, color; // предки, цвета
  57.  
  58. set<vi> cycle, box; // все циклы
  59. void add_cycle(int cycle_end, int cycle_st) {
  60.     vi curr_cycle, sorted;
  61.  
  62.     curr_cycle.push_back(cycle_st);
  63.     for (int v=cycle_end; v!=cycle_st; v=p[v])
  64.         curr_cycle.push_back(v);
  65.     sorted = curr_cycle; // создать копию без последнего элемента
  66.     curr_cycle.push_back(cycle_st);
  67.  
  68.     sort (sorted.begin(), sorted.end());
  69.  
  70.     // неориентированный граф
  71.     // избавляюсь от вырожденности (v - to - v)
  72.     if (curr_cycle.size()>3 && count(box.begin(), box.end(), sorted)==0) {
  73.         cycle.insert(curr_cycle);
  74.         box.insert(sorted);
  75.     }
  76. }
  77.  
  78. void dfs(int v) {
  79.     color[v] = 1;
  80.     for (int to: g[v]) {
  81.         if (color[to] == 0) {
  82.             p[to] = v;
  83.             dfs(to);
  84.         } else if (color[to] == 1) {
  85.             add_cycle(v, to);
  86.         }
  87.     }
  88.     color[v] = 0;
  89. }
  90.  
  91. void find_cycles() {
  92.     for (int i=1; i<=n; i++)
  93.         if (color[i] == 0)
  94.             dfs(i);
  95. }
  96.  
  97. int main() {
  98.     cin >> n;
  99.     points.assign(n, Point(0, 0));
  100.     vecs.assign(n, vv(n, Vector(0, 0)));
  101.     for (Point &p: points) cin >> p;
  102.  
  103.     // храню по длине количество ребер и точки
  104.     map<int, pair<int, vector< pair<int, int> > > > lens;
  105.     for (int i=0; i<n; i++) {
  106.         for (int j=0; j<n; j++) {
  107.             if (i == j) continue;
  108.             vecs[i][j] = Vector(points[i], points[j]);
  109.             vecs[j][i] = vecs[i][j];
  110.  
  111.             lens[vecs[i][j].dist2()].first++;
  112.             lens[vecs[i][j].dist2()].second.push_back({i, j});
  113.         }
  114.     }
  115.  
  116.     for (auto spec: lens) {
  117.         if (spec.second.first < 6) continue;
  118.         tn = spec.second.second.size() * 2; // максимальное количество точек в новом графе
  119.        
  120.         g.assign(tn + 1, vi());
  121.         p.assign(tn + 1, 0);
  122.         color.assign(tn + 1, 0);
  123.  
  124.         for (auto arr: spec.second.second) {
  125.             // тут нужно доделать (что бы не повторялись точки)
  126.             int v=arr.first+1, u=arr.second+1;
  127.             g[v].push_back(u);
  128.             g[u].push_back(v);
  129.         }
  130.  
  131.         cycle.clear();
  132.         box.clear();
  133.  
  134.         find_cycles();
  135.  
  136.         for (auto cyc: cycle) {
  137.             cout << '\n';
  138.             cout << "[len: " << spec.first << "] ";
  139.             for (auto v : cyc)
  140.                 cout << v << ' ';
  141.         }
  142.     }
  143. }
  144.  
  145. /*
  146. 13
  147. 2 2
  148. 7 4
  149. 9 5
  150. 10 7
  151. 9 11
  152. 7 12
  153. 5 11
  154. 4 9
  155. 5 5
  156. 1 7
  157. 12 4
  158. 13 9
  159. 6 8
  160. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement