Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2014
38
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.59 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. using namespace std;
  6.  
  7. struct pt {
  8.         double x, y;
  9. };
  10.  
  11. bool cmp (pt a, pt b) {
  12.     return a.x < b.x || a.x == b.x && a.y < b.y;
  13. }
  14.  
  15. bool cw (pt a, pt b, pt c) {
  16.     return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
  17. }
  18.  
  19. bool ccw (pt a, pt b, pt c) {
  20.     return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
  21. }
  22.  
  23. void Pirimier(vector<pt> pointlist)
  24. {
  25.     float result(0.0);
  26.     for (int i = 1; i < pointlist.size(); i++)
  27.     {
  28.         result += sqrt(pow((pointlist[i].x - pointlist[i-1].x),2) + pow((pointlist[i].y - pointlist[i-1].y),2));
  29.     }
  30.  
  31.     result += sqrt(pow((pointlist[pointlist.size() - 1].x - pointlist[0].x),2) + pow((pointlist[pointlist.size() - 1].y - pointlist[0].y),2));
  32.     printf("%f\n",result);
  33. }
  34.  
  35. void Square (vector<pt> pointlist)
  36. {
  37.     float result(0.0);
  38.     pt M;
  39.     M.x = 0; M.y = 0;
  40.  
  41.     pt MAi;
  42.     pt MAi_1;
  43.  
  44.     for (int i = 0; i < pointlist.size()-1; i++)
  45.     {
  46.         MAi.x = pointlist[i].x;
  47.         MAi.y = pointlist[i].y;
  48.  
  49.         MAi_1.x =  pointlist[i+1].x;
  50.         MAi_1.y =  pointlist[i+1].y;
  51.         result += (MAi.x*MAi_1.y - MAi_1.x*MAi.y);
  52.     }
  53.  
  54.     MAi.x = pointlist[pointlist.size()-1].x;
  55.     MAi.y = pointlist[pointlist.size()-1].y;
  56.  
  57.     MAi_1.x =  pointlist[0].x;
  58.     MAi_1.y =  pointlist[0].y;
  59.  
  60.     result += (MAi.x*MAi_1.y - MAi_1.x*MAi.y);
  61.  
  62.     printf("%f\n",abs(result)/2.0);
  63. }
  64.  
  65. void convex_hull (vector<pt> & a) {
  66.     if (a.size() == 1)  return;
  67.     sort (a.begin(), a.end(), &cmp);
  68.     pt p1 = a[0],  p2 = a.back();
  69.     vector<pt> up, down;
  70.     up.push_back (p1);
  71.     down.push_back (p1);
  72.     for (size_t i=1; i<a.size(); ++i) {
  73.         if (i==a.size()-1 || cw (p1, a[i], p2)) {
  74.             while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
  75.                 up.pop_back();
  76.             up.push_back (a[i]);
  77.         }
  78.         if (i==a.size()-1 || ccw (p1, a[i], p2)) {
  79.             while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
  80.                 down.pop_back();
  81.             down.push_back (a[i]);
  82.         }
  83.     }
  84.     a.clear();
  85.     for (size_t i=0; i<up.size(); ++i)
  86.         a.push_back (up[i]);
  87.     for (size_t i=down.size()-2; i>0; --i)
  88.         a.push_back (down[i]);
  89.  
  90.     Pirimier(a);
  91.     Square(a);
  92. }
  93.  
  94. int main()
  95. {
  96.     int size(0);
  97.     cin >> size;
  98.  
  99.     vector<pt> point;
  100.  
  101.     for (int i = 0; i < size; i++)
  102.     {
  103.         pt buf;
  104.         cin >> buf.x;
  105.         cin >> buf.y;
  106.  
  107.         point.push_back(buf);
  108.  
  109.     }
  110.  
  111.     convex_hull(point);
  112.     return 0;
  113. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement