erek1e

BIO 2018 Round 2 Problem 4 - Cables

Feb 14th, 2021 (edited)
272
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.08 KB | None | 0 0
  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.  
Add Comment
Please, Sign In to add comment