fork download
copy 
  1. //
  2. //    Построение выпуклой оболочки и вывод координат точек, входящих в нее, в порядке обхода против часовой стрелки
  3. //    
  4.  
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <vector>
  8. #include <algorithm>
  9. #include <cmath>
  10. #include <cassert>
  11.  
  12. typedef long double Real;
  13. typedef long long Int;
  14.  
  15. struct Point {
  16.     int x, y, id; // Координаты и порядковый номер точки
  17.  
  18.     Int norm2() const { // Квадрат нормы
  19.         return Int(x)*x+Int(y)*y;
  20.     }
  21.  
  22.     Point operator-(const Point& p) const { // Разность точек
  23.         return Point{x-p.x, y-p.y, 0};
  24.     }
  25. };
  26.  
  27. // Векторное произведение вектора a на вектор b:
  28. Int cross(const Point& a, const Point& b) {
  29.     return Int(a.x) * b.y - Int(a.y) * b.x;
  30. }
  31.  
  32. // Определение правого поворота:
  33. bool right_rotate(const Point& a, const Point& b, const Point& c) {
  34.     return cross(a-b, c-b) >= 0;
  35. }
  36.  
  37. int main() {
  38.     std::ios_base::sync_with_stdio(false);
  39.     std::cin.tie(0); std::cout.tie(0);
  40.  
  41.     // Чтение точек:
  42.     int n; std::cin >> n;
  43.     std::vector<Point> points;
  44.     for (int i = 1; i <= n; ++i) {
  45.         int x, y; 
  46.         std::cin >> x >> y;
  47.         points.push_back(Point{x, y, i});
  48.     }
  49.     // Нахождение самой левой точки:
  50.     auto it = min_element(points.begin(), points.end(), [](const Point& a, const Point& b){
  51.         return a.x < b.x || (a.x == b.x && a.y < b.y);
  52.     });
  53.     std::swap(*it, points[0]);
  54.  
  55.     // Сортировка точек по полярному углу относительно самой левой:
  56.     const Point& first = points[0];
  57.     std::sort(points.begin()+1, points.end(), [first](const Point& a, const Point& b) {
  58.         auto vector_a = a - first;
  59.         auto vector_b = b - first;
  60.         auto angle1 = std::atan2((Real)vector_a.y, (Real)vector_a.x);
  61.         auto angle2 = std::atan2((Real)vector_b.y, (Real)vector_b.x);
  62.         return angle1 < angle2 || (angle1 == angle2 && vector_a.norm2() < vector_b.norm2());
  63.     });
  64.     points.push_back(points[0]); // дублирование самой левой точки для замкнутости
  65.  
  66.     // Построение выпуклой оболочки:
  67.     std::vector<Point> convex_hull{points[0], points[1]};
  68.     for (int i = 2; i <= n; ++i) {
  69.         convex_hull.push_back(points[i]);
  70.         for (int j = (int)convex_hull.size()-1; j >= 2; --j) {
  71.             if (right_rotate(convex_hull[j-2], convex_hull[j-1], convex_hull[j])) {
  72.                 convex_hull[j-1] = convex_hull[j];
  73.                 convex_hull.pop_back();
  74.             } else {
  75.                 break;
  76.             }
  77.         }
  78.     }
  79.     // Проверка на невырожденность:
  80.     // assert(convex_hull.size() >= 4u); 
  81.  
  82.     // Проверка на замкнутость:
  83.     assert(convex_hull.front().id == convex_hull.back().id);
  84.     convex_hull.pop_back();
  85.  
  86.     // Вывод выпуклой оболочки:
  87.     std::cout << (int)convex_hull.size() << std::endl;
  88.     for (const auto& it : convex_hull) {
  89.         std::cout << (int)it.x << ' ' << (int)it.y << '\n';
  90.     }
  91.  
  92.     return 0;
  93. }
Success #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
3
0 0
1 -999999999 
1 -1000000000
stdout
copy 
3
0 0
1 -1000000000
1 -999999999
https://ideone.com/eOZd1t
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!