fork download
  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
stdin
3
0 0
1 -999999999 
1 -1000000000
stdout
1
0 0