# BIO 2018 Round 2 Problem 4 - Cables

Feb 14th, 2021 (edited)
343
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4. #include <cmath>
5.
6. using namespace std;
7.
8. struct Point {
9.     int x, y, i;
10.     bool operator == (const Point &p2) const {
11.         return x==p2.x && y==p2.y;
12.     }
13. };
14.
15. int main() {
16.     int s, l; cin >> s >> l;
17.     vector<Point> p(s*l);
18.     for (int i = 0; i < s*l; ++i) {
19.         cin >> p[i].x >> p[i].y;
20.         p[i].i = i+1;
21.     }
22.     sort(p.begin(), p.end(), [](const Point &p1, const Point &p2) {
23.          return pair<int, int>(p1.x, p1.y) < pair<int, int>(p2.x, p2.y);
24.     });
25.     for (int i = 0; i < l; ++i) {
26.         vector<Point> loop(s);
27.         for (int j = 0; j < s; ++j) loop[j] = p[s*i + j];
28.         Point pivot(loop[0]);
29.         sort(loop.begin(), loop.end(), [&pivot](const Point &p1, const Point &p2) {
30.              if (p2 == pivot) return false;
31.              if (p1 == pivot) return true;
32.              return atan2(p1.y - pivot.y, p1.x - pivot.x) < atan2(p2.y - pivot.y, p2.x - pivot.x);
33.         });
34.         for (Point pnt : loop) cout << pnt.i << ' ';
35.         cout << endl;
36.     }
37.     return 0;
38. }
39.