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