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<pair<int, complex< double> > >vz;
  9. typedef pair<int, complex<double> > pr;
  10. typedef complex<double> cx;
  11. bool compy(pr a, pr b)
  12. {
  13.     if(imag(a.second) < imag(b.second))  return true;
  14.     else if(imag(a.second) == imag(b.second)) return real(a.second) < real(b.second);
  15.     return false;
  16. }
  17. bool compol(pr a, pr b)
  18. {
  19.         return arg(a.second) < arg(b.second);
  20. }
  21.  
  22. void update(vz &v, pr ausi, int mode)
  23. {
  24.     if(mode  == 1)
  25.     for(int i = 0 ; i < v.size() ; ++i)
  26.     {
  27.        v[i].second -= ausi.second;
  28.     }
  29.     else
  30.     for(int i = 0 ; i < v.size() ; ++i)
  31.     {
  32.         v[i].second += ausi.second;
  33.     }
  34. }
  35. double area(pr a, pr b, pr c)
  36. {
  37.     return (real(b.second) - real(a.second))*(imag(c.second) - imag(b.second)) - (real(c.second) - real(b.second))*(imag(b.second) - imag(a.second));
  38. }
  39. double perimeter(vz &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].second) - real(hull[i].second))*(real(hull[i+1].second) - real(hull[i].second)) + (imag(hull[i+1].second) - imag(hull[i].second))*(imag(hull[i+1].second) - imag(hull[i].second)));
  46.         peri += x;
  47.     }
  48.  
  49.     x = sqrt((real(hull[i].second) - real(hull[0].second))*(real(hull[i].second) - real(hull[0].second)) + (imag(hull[i].second) - imag(hull[0].second))*(imag(hull[i].second) - imag(hull[0].second)));
  50.     peri += x;
  51.     return peri;
  52. }
  53. int main()
  54. {
  55.     int n, T, i=0, x, y;
  56.     vz z, hull;
  57.     cx ausi;
  58.     vector<int> id;
  59. //      freopen("ip.txt", "r", stdin);
  60. //      freopen("op.txt", "w", stdout);
  61.     cin>>T;
  62.     while(T--)
  63.     {
  64.         cin>>n;
  65.          if(n == 1)
  66.         {
  67.             cin>>x>>y;
  68.             cout<<"0.00"<<endl<<1<<endl;
  69.         }
  70.         else
  71.     {
  72.         id.clear();
  73.         hull.clear();
  74.     z.clear();
  75.     i = 0;
  76.     while(i < n)
  77.     {
  78.         cin>>x>>y;
  79.         ausi = complex<double> (x, y);
  80.         z.push_back(make_pair(++i, ausi));
  81.     }
  82. sort(z.begin(), z.end(), compy);
  83. pr ausi = z[0];
  84.  
  85. /** translate all the points wrt base point **/
  86. update(z, ausi, 1);
  87.  
  88. /**sort all the points wrt polar angle**/
  89.  stable_sort(z.begin(), z.end(), compol);
  90. /**reset all the points **/
  91. update(z, ausi, 0);
  92.  
  93. /**lets make the hull**/
  94. hull.push_back(z[0]);   id.push_back(z[0].first);
  95. hull.push_back(z[1]);   id.push_back(z[1].first);
  96. size_t szz = z.size();
  97. size_t szh = hull.size();
  98.     int j;
  99. //    cout<<"\nthe points in order are :\n";
  100. //    for(auto it : z)
  101. //        cout<<it.first<<' '<<it.second<<endl;
  102. for(j = 2 ; j <szz ; ++j)
  103. {
  104.     while(area(hull[szh-2], hull[szh-1], z[j])<=0.0)
  105.         {
  106.             hull.pop_back();
  107.             szh--;
  108.             id.pop_back();
  109.             if(szh == 1)
  110.                 break;
  111.         }
  112.             hull.push_back(z[j]);
  113.             id.push_back(z[j].first);
  114.             szh++;
  115. }
  116.     printf("%.2f", perimeter(hull));
  117.     cout<<"\n";
  118.     for(int i=0;i<id.size(); ++i)
  119.         cout<<id[i]<<' ';
  120.     cout<<endl<<endl;
  121.     }
  122.     }
  123.   return 0;
  124. }
  125.  
  126.  
  127.  
Success #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
8

5
0 0
0 5
10 5
3 3
10 0

1
0 0

3
0 0
1 0
2 0

4
0 0
0 0
0 1
1 0

3
0 0
0 1
1 0

6
0 0
-1 -1
1 1
2 2
3 3
4 4

2
10 0
0 0

7
-3 -4
2 -3
4 3
-4 2
0 5
2 -3
-1 4
stdout
copy 
30.00
1 5 3 2 

0.00
1
4.00
1 3 

3.41
1 4 3 

3.41
1 3 2 

14.14
2 6 

20.00
2 1 

26.98
1 6 3 5 4
https://ideone.com/4Z7RHX
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!