fork(2) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <queue>
  4. #include <cstdlib>
  5. #include <cstring>
  6. #include <cmath>
  7. #include <algorithm>
  8. #include <string>
  9. #include <climits>
  10. #include <vector>
  11. #include <deque>
  12. #include <set>
  13. #include <map>
  14. #include <list>
  15. #include <stack>
  16. #include <cctype>
  17. #include <bitset>
  18. #include <ctime>
  19. #include <fstream>
  20. #include <iomanip>
  21. using namespace std;
  22.  
  23. /*
  24. ifstream in("hull.in");
  25. ofstream out("hull.out");
  26.  
  27. #define cin in
  28. #define cout out
  29. */
  30.  
  31. #define MIN(x,y) (((x)<(y))?(x):(y))
  32. #define MAX(x,y) (((x)>(y))?(x):(y))
  33. #define ABS(x) (((x)<0)?(-(x)):(x))
  34. typedef long long ll;
  35. typedef unsigned long long ull;
  36. typedef long double ld;
  37. const ld EPS = 0.0000001;
  38. const ld PI  = 3.141592653589793;
  39.  
  40. const int MAX_N = 111111;
  41. int N, L, c_hull_ptr = 0;
  42.  
  43. struct Point{
  44.     int x, y;
  45.  
  46.     Point& operator=(const Point& p) {
  47.         x = p.x; y = p.y;
  48.         return *this;
  49.     }
  50. } points[MAX_N], c_hull[MAX_N], P;
  51.  
  52. bool cmp(const Point& p1, const Point& p2) {
  53.     // maybe, float's precision isn't enough?
  54.     float deltaY1 = p1.y - P.y, deltaY2 = p2.y - P.y;
  55.     float deltaX1 = p1.x - P.y, deltaX2 = p2.x - P.x;
  56.  
  57.     float angle1 = atan2(deltaY1, deltaX1);
  58.     float angle2 = atan2(deltaY2, deltaX2);
  59.  
  60.     if(angle1 < 0.0) angle1 += 2.0 * PI;
  61.     if(angle2 < 0.0) angle2 += 2.0 * PI;
  62.  
  63.     if(angle1 == angle2)
  64.         if(p1.y != p2.y)
  65.             return p1.y < p2.y;
  66.         else if(p1.x != p2.x)
  67.             return p1.x < p2.x;
  68.  
  69.     return angle1 < angle2;
  70. }
  71.  
  72. void input() {  // & searching for the starting point
  73.     cin >> N;
  74.     P.x = P.y = (1<<31)-1;
  75.     for(int i = 0; i < N; ++i) {
  76.         cin >> points[i].x >> points[i].y;
  77.         if(points[i].y < P.y)
  78.             P = points[i];
  79.         else if(points[i].y == P.y and points[i].x < P.x)
  80.             P = points[i];
  81.     }
  82. }
  83.  
  84. bool left_turn(Point& p1, Point& p2, Point& p3) {
  85.     return (p1.x*p2.y + p3.x*p1.y + p2.x*p3.y - p3.x*p2.y - p1.x*p3.y - p2.x*p1.y) > 0;
  86. }
  87.  
  88. void convex_hull() {
  89.     sort(points, points + N, cmp);
  90.  
  91.     points[N++] = points[0];
  92.  
  93.     // inserting first two points
  94.     c_hull[c_hull_ptr++] = points[0];
  95.     c_hull[c_hull_ptr++] = points[1];
  96.  
  97.     // building convex hull
  98.     for(int i = 2; i <= N; ++i) {
  99.         if(!left_turn(c_hull[c_hull_ptr - 2], c_hull[c_hull_ptr - 1], points[i]))
  100.             c_hull_ptr--;
  101.  
  102.         c_hull[c_hull_ptr++] = points[i];
  103.     }
  104.  
  105.     // print result
  106.     cout << c_hull_ptr - 1 << '\n';
  107.     for(int i = 0; i < c_hull_ptr - 1; ++i)
  108.         cout << c_hull[i].x << " " << c_hull[i].y << '\n';
  109. }
  110.  
  111. int main() {
  112.     ios_base::sync_with_stdio(0);
  113.     srand(time(0));
  114.  
  115.     input();
  116.     convex_hull();
  117.  
  118.     return 0;
  119. }
  120.  
Success #stdin #stdout 0s 5216KB
comments (?)
stdin
copy 
5
0 0
2 0
0 2
1 1
2 2
stdout
copy 
4
0 0
2 0
2 2
0 2
https://ideone.com/IXFfS9
language:
C++ (gcc 8.3)
created:
10 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!