fork download
copy 
  1. // Devarshi
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define mp make_pair
  7. #define mt make_tuple
  8. #define fi first
  9. #define se second
  10. #define pb push_back
  11. #define ll long long
  12. #define all(x) (x).begin(), (x).end()
  13. #define rall(x) (x).rbegin(), (x).rend()
  14. #define rep(i,n) for(i=0;i<n;i++)
  15. #define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
  16. #define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
  17. #define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
  18. #define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
  19. #define fora(it,x) for(auto it:x)
  20. #define PI 3.14159265
  21. #define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  22.  
  23. typedef pair<ll, ll> pii;
  24. typedef vector<ll> vi;
  25. typedef vector<pii> vpi;
  26. typedef vector<vi> vvi;
  27. typedef long long i64;
  28. typedef vector<i64> vi64;
  29. typedef vector<vi64> vvi64;
  30. typedef pair<i64, i64> pi64;
  31. typedef double ld;
  32.  
  33. template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
  34. template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }
  35.  
  36. const int maxn=1000001;
  37.  
  38. bool cw(pair<int,pair<ld,ld> > a,pair<int,pair<ld,ld> > b,pair<int,pair<ld,ld> > c){
  39.     return a.se.fi*(b.se.se-c.se.se)+b.se.fi*(c.se.se-a.se.se)+c.se.fi*(a.se.se-b.se.se) < 0;
  40. }
  41.  
  42. bool ccw(pair<int,pair<ld,ld> > a,pair<int,pair<ld,ld> > b,pair<int,pair<ld,ld> > c){
  43.     return a.se.fi*(b.se.se-c.se.se)+b.se.fi*(c.se.se-a.se.se)+c.se.fi*(a.se.se-b.se.se) > 0;
  44. }
  45.  
  46. bool cmp(pair<int,pair<ld,ld> > a,pair<int,pair<ld,ld> > b){
  47.     if(a.se.se==b.se.se && a.se.fi!=b.se.fi) return a.se.fi<b.se.fi;
  48.     if(a.se.fi==b.se.fi) return a.fi<b.fi;
  49.     return a.se.se<b.se.se;
  50. }
  51.  
  52. ld dist(pair<int,pair<ld,ld> > a,pair<int,pair<ld,ld> > b){
  53.     ld x=a.se.fi-b.se.fi;
  54.     x*=x;
  55.     ld y=b.se.se-a.se.se;
  56.     y*=y;
  57.     return sqrt(x+y);
  58. }
  59.  
  60. int main(){
  61.  
  62. sync
  63. /*
  64. #ifndef ONLINE_JUDGE
  65.     // for getting input from input.txt
  66.     freopen("input.txt", "r", stdin);
  67.     // for writing output to output.txt
  68.     freopen("output.txt", "w", stdout);
  69. #endif
  70. */
  71. int t;
  72. cin>>t;
  73. while(t--){
  74.  
  75. int n;
  76. cin>>n;
  77.  vector<pair<int,pair<ld,ld> > > pts(n);
  78. map< pair<ld,ld> ,int > m;
  79.  forn(i,n) {
  80.     pts[i].fi = i+1;
  81.     cin>>pts[i].se.fi;
  82.     cin>>pts[i].se.se;
  83.     if(m.find(mp(pts[i].se.fi,pts[i].se.se))==m.end()){
  84.         m[mp(pts[i].se.fi,pts[i].se.se)]=i+1;
  85.     }
  86. }
  87.  
  88. sort(all(pts),cmp);
  89.  
  90. pair<int,pair<ld,ld> > a,b;
  91. a.fi=pts[0].fi;
  92. a.se.se=pts[0].se.se;
  93. a.se.fi=pts[0].se.fi;
  94.  
  95. b.fi=pts[n-1].fi;
  96. b.se.se=pts[n-1].se.se;
  97. b.se.fi=pts[n-1].se.fi;
  98.  
  99. vector<pair<int,pair<ld,ld> >> up,down;
  100. up.pb(a);
  101. down.pb(a);
  102. fore(i,1,n-1){
  103.    // pair <int,int> p(pts[i].se.fi,pts[i].se.se);
  104.     if(i==n-1||cw(a,pts[i],b)){
  105.  
  106.         while(up.size()>=2 && !cw(up[up.size()-2],up[up.size()-1],pts[i])){
  107.             up.pop_back();
  108.         }
  109.  
  110.         up.pb(pts[i]);
  111.     }
  112.     if(i==n-1||ccw(a,pts[i],b)){
  113.  
  114.         while(down.size()>=2 && !ccw(down[down.size()-2],down[down.size()-1],pts[i])){
  115.             down.pop_back();
  116.         }
  117.  
  118.         down.pb(pts[i]);
  119.     }
  120.  
  121. }
  122.  
  123. reverse(all(up));
  124.  
  125. vector<pair<int,pair<ld,ld> > > ans;
  126.  
  127. ld peri = 0;
  128.  
  129. fore(i,1,down.size()-1){
  130.     peri += dist(down[i],down[i-1]);
  131. }
  132. fore(i,1,up.size()-1){
  133.     peri += dist(up[i],up[i-1]);
  134. }
  135.  
  136. cout<<fixed<<setprecision(2)<<peri<<endl;
  137.  
  138. for(auto it:down){
  139.     cout<<m[mp(it.se.fi,it.se.se)]<<" ";
  140. }
  141. fore(i,1,up.size()-2){
  142.     cout<<m[mp(up[i].se.fi,up[i].se.se)]<<" ";
  143. }
  144.  
  145. cout<<endl<<endl;
  146.  
  147. }
  148.  
  149. return 0;
  150. }
  151.  
Success #stdin #stdout 0s 15248KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/OpAj4u
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!