Advertisement
Guest User

Untitled

a guest
Feb 6th, 2014
148
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.60 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cmath>
  5. #include <cstdio>
  6.  
  7. using namespace std;
  8.  
  9. #define pii pair<int,int>
  10. #define mp make_pair
  11. #define fi first
  12. #define se second
  13.  
  14. pii a[1000];
  15. pii m;
  16.  
  17. double dist(pii a, pii b)
  18. {
  19.     return sqrt((a.fi-b.fi)*(a.fi-b.fi) + (a.se-b.se)*(a.se-b.se));
  20. }
  21.  
  22. bool sr(pii m, pii a, pii b)
  23. {
  24.     int t = (m.fi-a.fi)*(m.se+a.se)+(a.fi-b.fi)*(a.se+b.se)+(b.fi-m.fi)*(b.se+m.se);
  25.     if (t != 0)
  26.     {
  27.         return t > 0;
  28.     }
  29.     else
  30.     {
  31.         return dist(m,a) > dist(m,b);
  32.     }
  33. }
  34.  
  35. bool srr(pii a, pii b)
  36. {
  37.     return sr(m,a,b);
  38. }
  39.  
  40. int main()
  41. {
  42.     int n,x,y;
  43.     scanf("%d",&n);
  44.     for (int i = 0; i < n; i++)
  45.     {
  46.         scanf("%d%d",&x,&y);
  47.         a[i] = mp(x,y);
  48.     }
  49.     m = a[0];
  50.     for (int i = 0; i < n; i++)
  51.     {
  52.         if (m.fi > a[i].fi)
  53.         {
  54.             m = a[i];
  55.         }
  56.         else if (m.fi == a[i].fi && m.se > a[i].se)
  57.         {
  58.             m = a[i];
  59.         }
  60.     }
  61.     sort(a,a+n,srr);
  62.     vector<pii> v;
  63.     for (int i = 0; i < n; i++)
  64.     {
  65.         if (v.size() < 2)
  66.         {
  67.             v.push_back(a[i]);
  68.         }
  69.         else
  70.         {
  71.             if (!sr(v[v.size()-2],v[v.size()-1],a[i]))
  72.             {
  73.                 v.pop_back();
  74.                 i--;
  75.             }
  76.             else
  77.             {
  78.                 v.push_back(a[i]);
  79.             }
  80.         }
  81.     }
  82.     double res = 0;
  83.     for (int i = 0; i < v.size()-1; i++) res += dist(v[i],v[i+1]);
  84.     res += dist(v[0],v[v.size()-1]);
  85.     cout.precision(20);
  86.     cout << res;
  87.     return 0;
  88. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement