fork(4) download
copy 
  1. /*
  2.   Copyright 2013 Marek "p2004a" Rusinowski
  3.   Graham scan
  4. */
  5. #include <cstdio>
  6. #include <vector>
  7. #include <algorithm>
  8.  
  9. using namespace std;
  10.  
  11. class point {
  12.  public:
  13.   int x, y;
  14.   point(int _x, int _y) : x(_x), y(_y) {}
  15. };
  16.  
  17. inline int det(const point &p0, const point &p1, const point p2) {
  18.   return (p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y);
  19. }
  20.  
  21. inline int d(const point &p1, const point &p2) {
  22.   return (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
  23. }
  24.  
  25. class comp {
  26.   point p0;
  27.  public:
  28.   comp(const point &p) : p0(p) {}
  29.   bool operator() (const point &p1, const point &p2) {
  30.     int t = det(p0, p1, p2);
  31.     if (t > 0) return true;
  32.     if (t < 0) return false;
  33.     return d(p0, p1) < d(p0, p2);
  34.   }
  35. };
  36.  
  37. vector<point> graham(vector<point> points) {
  38.   int idx = 0;
  39.   for (int i = 1; i < (int)points.size(); ++i) {
  40.     if (points[i].y < points[idx].y || (points[i].y == points[idx].y && points[i].x < points[idx].x)) idx = i;
  41.   }
  42.   swap(points.back(), points[idx]);
  43.   vector<point> out;
  44.   out.push_back(points.back());
  45.   points.pop_back();
  46.   comp cmp(out[0]);
  47.   sort(points.begin(), points.end(), cmp);
  48.  
  49.   for (int i = 0; i < (int) points.size(); ++i) {
  50.     while (out.size() >= 2 && det(out[out.size() - 2], out.back(), points[i]) < 0) {
  51.       out.pop_back();
  52.     }
  53.     out.push_back(points[i]);
  54.   }
  55.  
  56.   return out;
  57. }
  58.  
  59. int main() {
  60.   int n;
  61.   scanf("%d", &n);
  62.   vector<point> points;
  63.   for (int i = 0; i < n; ++i) {
  64.     int a, b;
  65.     scanf("%d%d", &a, &b);
  66.     points.push_back(point(a, b));
  67.   }
  68.   vector<point> out = graham(points);
  69.  
  70.   for (int i = 0; i < (int) out.size(); ++i) {
  71.     printf("%d %d\n", out[i].x, out[i].y);
  72.   }
  73.   return 0;
  74. }
  75.  
Success #stdin #stdout 0s 3036KB
comments (?)
stdin
copy 
10
1 7
7 -1
2 3
0 2
-8 0
8 5
-1 1
-10 -1
7 -6
7 5
stdout
copy 
7 -6
8 5
1 7
-10 -1
https://ideone.com/9pateB
language:
C++ (gcc 8.3)
created:
11 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!