fork download
copy 
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <cmath>
  6. #include <cassert>
  7.  
  8. struct Point {
  9.     long long x, y;
  10.     int id;
  11.  
  12.     long long norm2() const {
  13.         return x*x+y*y;
  14.     }
  15.  
  16.     Point operator-(const Point& p) const {
  17.         return Point{x-p.x, y-p.y, 0};
  18.     }
  19. };
  20.  
  21. long long det(const Point& a, const Point& b) {
  22.     return a.x * b.y - a.y * b.x;
  23. }
  24.  
  25. bool right_rotate(const Point& a, const Point& b, const Point& c) {
  26.     return det(a-b, c-b) >= 0;
  27. }
  28.  
  29. int main() {
  30.     std::ios_base::sync_with_stdio(false);
  31.     std::cin.tie(0); std::cout.tie(0);
  32.     int n; std::cin >> n;
  33.     std::vector<Point> points;
  34.     for (int i = 1; i <= n; ++i) {
  35.         long long x, y; std::cin >> x >> y;
  36.         points.push_back(Point{x, y, i});
  37.     }
  38.  
  39.     auto it = min_element(points.begin(), points.end(), [](const Point& a, const Point& b){
  40.         return a.x < b.x || (a.x == b.x && a.y < b.y);
  41.     });
  42.     std::swap(*it, points[0]);
  43.     for (int i = 1; i < n; ++i) {
  44.         points[i].x -= points[0].x;
  45.         points[i].y -= points[0].y;
  46.     }
  47.     points[0].x = points[0].y = 0;
  48.     std::sort(points.begin()+1, points.end(), [](const Point& a, const Point& b) {
  49.         return a.y * b.x < b.y * a.x || (a.y * b.x == b.y * a.x && a.norm2() < b.norm2());
  50.     });
  51.     points.push_back(points[0]);
  52.     std::vector<Point> conv_hull{points[0], points[1]};
  53.     for (int i = 2; i <= n; ++i) {
  54.         conv_hull.push_back(points[i]);
  55.         for (int j = (int)conv_hull.size()-1; j >= 2; --j) {
  56.             if (right_rotate(conv_hull[j-2], conv_hull[j-1], conv_hull[j])) {
  57.                 conv_hull[j-1] = conv_hull[j];
  58.                 conv_hull.pop_back();
  59.             } else {
  60.                 break;
  61.             }
  62.         }
  63.     }
  64.  
  65.     assert(conv_hull.size() >= 4u);
  66.     assert(conv_hull.front().id == conv_hull.back().id);
  67.  
  68.  
  69.     std::cout << (int)conv_hull.size()-1 << std::endl;
  70.     for (int i = 0; i+1 < (int)conv_hull.size(); ++i) {
  71.         const auto& it = conv_hull[i];
  72.         std::cout << (int)it.x << ' ' << (int)it.y << '\n';
  73.     }
  74.  
  75.     return 0;
  76. }
Success #stdin #stdout 0s 4380KB
comments (?)
stdin
copy 
3
0 0
1 -999999999 
1 -1000000000
stdout
copy 
3
0 0
1 -1000000000
1 -999999999
https://ideone.com/F6SKI3
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!