fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. struct Point{
  6.     int x,y,n;
  7. }pts[100005];
  8.  
  9. Point p0;
  10. stack<Point> s;
  11. vector<int> v(100005);
  12.  
  13. void swap_pts(Point &u,Point &v){
  14.     Point temp = u;
  15.     u = v;
  16.     v = temp;
  17. }
  18.  
  19. int orientation(Point p,Point q,Point r)
  20. {
  21. 	int ans = (q.y-p.y)*(r.x-q.x) - (r.y - q.y)*(q.x-p.x);
  22. 	if( ans == 0) // colinear
  23. 		return 0;
  24. 	return ans < 0 ? 2 : 1; // anticlock / clockwise
  25. }
  26.  
  27. int distSq(Point a,Point b){
  28.     return (a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y);
  29. }
  30.  
  31. int compare(const void *a,const void  *b){
  32.     Point *u = (Point*) a;
  33.     Point *v = (Point*) b;
  34.     int val = orientation(p0,*u,*v);
  35.  
  36.     int dv = distSq(p0,*v);
  37.     int du = distSq(p0,*u);
  38.  
  39.     if(val == 2)
  40.         return -1;
  41.     else if(val == 0 && dv > du)
  42.         return -1;
  43.     else if(val == 0 && dv == du && (*v).n < (*u).n)
  44.         return -1;
  45.     else
  46.         return 1;
  47.  
  48. }
  49.  
  50. void printStack(){
  51.     p0 = s.top();s.pop();
  52.     Point p2 = p0,p1;
  53.     double p = 0.0;
  54.     int j=0;
  55.     v[j++] = p0.n;
  56.  
  57.     while(!s.empty()){
  58.         p1 = s.top();s.pop();
  59.         p += (double) sqrt(distSq(p2,p1));
  60.         p2 = p1;
  61.         v[j++] = p1.n;
  62.     }
  63.     p += (double) sqrt(distSq(p2,p0));
  64.     printf("%.2f\n",p);
  65.  
  66.     for(int i = j - 1; i >=0; i--)
  67.         printf("%d ",v[i]);
  68.     printf("\n\n");
  69. }
  70.  
  71. Point nextToTop(){
  72.     Point temp = s.top();
  73.     s.pop();
  74.     Point res = s.top();
  75.     s.push(temp);
  76.     return res;
  77. }
  78.  
  79. bool checkConditions(int n){
  80.     if(n==1){
  81.         printf("0.00\n1\n\n");
  82.         return false;
  83.     }else if(n==2){
  84.         double p  = (double) (2*sqrt(distSq(pts[0],pts[1])));
  85.         if(pts[1].y < pts[0].y || (pts[1].y==pts[0].y && pts[1].x < pts[0].x))
  86.             printf("%.2f\n%d %d\n\n",p,pts[1].n,pts[0].n);
  87.         else
  88.             printf("%.2f\n%d %d\n\n",p,pts[0].n,pts[1].n);
  89.         return false;
  90.     }else
  91.         return true;
  92. }
  93.  
  94. void convexHull(int n){
  95.     int minval = 0;
  96.     for(int i = 1; i < n; i++)
  97.         if((pts[i].y < pts[minval].y) || (pts[i].y == pts[minval].y && pts[i].x < pts[minval].x))
  98.             minval = i;
  99.  
  100.     swap_pts(pts[0],pts[minval]);
  101.     p0 = pts[minval];
  102.  
  103.     qsort(&pts[1], n-1, sizeof(Point), compare);
  104.  
  105.     int m = 1;
  106.     for(int i = 1; i < n; i++){
  107.         while(i < n-1 && (orientation(p0,pts[i],pts[i+1])==0))
  108.             i++;
  109.         pts[m] = pts[i];
  110.         m++;
  111.     }
  112.  
  113.     if(!checkConditions(m))
  114.         return;
  115.  
  116.     s.push(pts[0]);
  117.     s.push(pts[1]);
  118.     s.push(pts[2]);
  119.  
  120.     for(int i = 3; i < m; i++){
  121.         while(orientation(nextToTop(),s.top(),pts[i])!=2)
  122.             s.pop();
  123.         s.push(pts[i]);
  124.     }
  125.  
  126.     printStack();
  127. }
  128.  
  129. int main(){
  130.     int tc;
  131.     scanf("%d",&tc);
  132.     while(tc--){
  133.         int n;
  134.         scanf("%d",&n);
  135.         for(int i = 0; i < n; i++){
  136.             scanf("%d%d",&pts[i].x,&pts[i].y);
  137.             pts[i].n = i+1;
  138.         }
  139.  
  140.         if(checkConditions(n))
  141.             convexHull(n);
  142.  
  143.     }
  144.     return 0;
  145. }
Success #stdin #stdout 0s 4356KB
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 2 3 5 4
https://ideone.com/R1YNyk
language:
C++ (gcc 8.3)
created:
5 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!