fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5.  
  6. using namespace std; 
  7.  
  8. struct Point {
  9. 	double x,y; 
  10. 	bool operator== (const Point&p) const { return x==p.x && y==p.y; } 
  11. };
  12.  
  13. double perimeter(vector<Point> P)
  14. {
  15.     double r = 0;
  16.     for(int i = 1;i < P.size(); i++)
  17.         r += sqrt(pow(P[i].x - P[i-1].x, 2) + pow(P[i].y - P[i-1].y, 2));
  18.     return r;
  19. }
  20. int orientation(Point p, Point q, Point r)
  21. {
  22.     int val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
  23.  
  24.     if (val == 0) 
  25.         return 0;
  26.     return (val > 0) ? 1 : 2;
  27. }
  28.  
  29. int find_leftmost_point(vector<Point> points, int n)
  30. {
  31.     int l = 0;
  32.     for (int i = 1; i < n; i++)
  33.         if (points[i].x < points[l].x)
  34.             l = i;
  35.     return l;
  36.  
  37. }
  38.  
  39. vector<Point> convexHull(vector<Point> points, int base, vector<Point> &hull)
  40. {
  41.     int p, q;
  42.  
  43.     p = base;   
  44.     q = (p+1) % points.size();
  45.     if (points.size() <= 3) 
  46.     {
  47.         return hull;
  48.     }
  49.     if(q == base)  
  50.     {
  51.         return hull;
  52.     }
  53.     else
  54.     {   
  55.         for (int i = 0; i < points.size(); i++)
  56.         {   
  57.             if (orientation(points[p], points[i], points[q]) == 2)
  58.             {
  59.                 q = i;
  60.             }
  61.         }
  62.         auto srch=find(hull.begin(), hull.end(), points[q]); 
  63.         if (srch!=hull.end()) {
  64.         	cout << "ALREADY IN"<<endl; 
  65.         	return hull;
  66.         }
  67.         cout<<points[q].x<<","<<points[q].y<<endl;
  68.         hull.push_back(points[q]);
  69.         return convexHull(points, q, hull);
  70.     }
  71. }
  72.  
  73.  
  74. int main()
  75. {
  76.     vector<Point> hull(20);
  77.     int n,x,y;
  78.     cin >> n;
  79.     vector<Point> ps;
  80.     Point p;
  81. //  Point p1,p2,q1,q2;
  82.  
  83.     while(cin >> x >> y)
  84.     {   
  85.         p.x = x;
  86.         p.y = y;
  87.         ps.push_back(p);
  88.     }
  89.     int base = find_leftmost_point(ps, n);
  90.     hull.push_back(ps[base]);
  91.     vector<Point> po = convexHull(ps, base, hull);
  92.     cout << perimeter(po) << endl;
  93.     return 0;
  94. }
  95.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
5
10 30
20 20
19 10
8 5
2 20
stdout
copy 
8,5
19,10
20,20
10,30
ALREADY IN
72.5303
https://ideone.com/lICWUV
language:
C++14 (gcc 8.3)
created:
8 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!