fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #include<complex>
  3. #define fi(i, a, b) for(int i = a; i < b ; ++i)
  4. #define fd(i, a, b) for(int i = a; i < b ; --i)
  5.  
  6. using namespace::std;
  7.  
  8. typedef vector<complex< double> > vz;
  9. typedef complex<double> cx;
  10. //typedef complex<double>::iterator ct;
  11. bool compy(cx a, cx b)
  12. {
  13.     if(imag(a) < imag(b))  return true;
  14.     else if(imag(a) == imag(b)) return real(a) < real(b);
  15.     return false;
  16. }
  17. bool compol(cx a, cx b)
  18. {
  19.     return (arg(a) < arg(b));
  20. }
  21.  
  22. void update(vz &v, cx &ausi, int mode)
  23. {
  24.     if(mode  == 1)
  25.     for(int i = 0 ; i < v.size() ; ++i)
  26.     {
  27.        v[i] -= ausi;
  28.     }
  29.     else
  30.     for(int i = 0 ; i < v.size() ; ++i)
  31.     {
  32.         v[i] += ausi;
  33.     }
  34. }
  35. double area(cx a, cx b, cx c)
  36. {
  37.     return (real(b) - real(a))*(imag(c) - imag(b)) - (real(c) - real(b))*(imag(b) - imag(a));
  38. }
  39. double perimeter(vector<cx> &hull)
  40. {
  41.     int i;
  42.     double peri = 0.0, x = 0.0;
  43.     for(i = 0 ; i < hull.size() -1; ++i)
  44.     {
  45.         x = sqrt((real(hull[i+1]) - real(hull[i]))*(real(hull[i+1]) - real(hull[i])) + (imag(hull[i+1]) - imag(hull[i]))*(imag(hull[i+1]) - imag(hull[i])));
  46.         peri += x;
  47.     }
  48.  
  49.     x = sqrt((real(hull[i]) - real(hull[0]))*(real(hull[i]) - real(hull[0])) + (imag(hull[i]) - imag(hull[0]))*(imag(hull[i]) - imag(hull[0])));
  50.     peri += x;
  51.     return peri;
  52. }
  53. int main()
  54. {
  55.   int n, i = 0, x, y, T;
  56.   vector<complex<double> > z ;
  57.   complex<double> ausi;
  58.   vector<cx> hull;
  59. //  freopen("convex hull using complex no INP file.txt", "r", stdin);
  60. //      freopen("convex hull using complex no OUT file.txt", "w", stdout);
  61.  
  62. //        cout<<"\nenter the no of points : \t";
  63.     cin>>n;
  64.     hull.clear();
  65.     z.clear();
  66.     i = 0;
  67. //    cout<<"\nenter each point (x, y) :\n";
  68.     while(i < n)
  69.     {
  70.         cin>>x>>y;
  71.         ausi = complex<double> (x, y);
  72.         z.push_back(ausi);
  73.         i++;
  74.     }
  75. //cout<<"\nthe points in increasing ord of y co-ord (x co-ord breaks the tie ) are \n";
  76. sort(z.begin(), z.end(), compy);
  77. ausi = z[0];
  78.  
  79. /** translate all the points wrt base point **/
  80. update(z, ausi, 1);
  81.  
  82.  sort(z.begin(), z.end(), compol);
  83.  
  84. /**reset all the points **/
  85. update(z, ausi, 0);
  86.  
  87. /**lets make the hull**/
  88. hull.push_back(z[0]);
  89. hull.push_back(z[1]);
  90. size_t szz = z.size();
  91. size_t szh = hull.size();
  92. for(int i = 2 ; i <szz ; ++i)
  93. {
  94.     while(area(hull[szh-2], hull[szh-1], z[i])<=0.0)
  95.         {
  96.             hull.pop_back();
  97.             szh--;
  98.         }
  99.             hull.push_back(z[i]);
  100.             szh++;
  101. }
  102.     cout<<(int)perimeter(hull);
  103.   return 0;
  104. }
  105.  
  106.  
  107.  
Success #stdin #stdout 0s 3436KB
comments (?)
stdin
copy 
4
0 0
5 0 
1 1
0 5
stdout
copy 
17
https://ideone.com/4zJsSa
language:
C++14 (gcc 8.3)
created:
9 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!