fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<conio.h>
  4.  
  5. typedef struct Point
  6. {
  7.   int x,y;       
  8. }Point;
  9.  
  10. int direction(Point p0,Point p1,Point p2)
  11. {
  12.   return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
  13. }
  14.  
  15. int distSquared(Point a,Point b)
  16. {
  17.   return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
  18. }
  19.  
  20. int comp(Point p0,Point a, Point b)
  21. {
  22.   int d=direction(p0,a,b);
  23.   if(d!=0) return (d>0);
  24.   else return distSquared(p0,a) > distSquared(p0,b); 
  25. }
  26.  
  27. void heapify(int l,int r, Point *P)
  28. {
  29.      int i,j;
  30.      Point t;
  31.      int isHeap;
  32.      t=P[l];
  33.      i=l;
  34.      j=2*i;
  35.      isHeap=0;
  36.      while(j<=r && !isHeap)
  37.      {
  38.        if(j<r && comp(P[0],P[j],P[j+1])) 
  39.           j++;
  40.        if(comp(P[0],t,P[j]))
  41.        {
  42.             P[i]=P[j];
  43.             i=j;
  44.             j=2*i;
  45.        }
  46.        else 
  47.             isHeap=1;
  48.      }
  49.      P[i]=t;
  50. }
  51.  
  52. void buildHeap(int n,Point *P)
  53. {
  54. int i;
  55.    for(i=n/2;i>=1;i--)
  56.       heapify(i,n,P);
  57. }
  58.  
  59. void heapSort(int n,Point *P)
  60. {
  61. int i;
  62. Point t;
  63.     buildHeap(n,P); 
  64.     for(i=n;i>=2;i--)
  65.     {
  66.         t=P[1];
  67.         P[1]=P[i];
  68.         P[i]=t;
  69.         heapify(1,i-1,P);
  70.     }                 
  71. }
  72.  
  73. int removeDuplicates(int size, Point *P)
  74. {
  75. int i,prev,count;
  76.     prev=1;
  77.     for(i=1;i<size;i++)
  78.     {
  79.        if(direction(P[0],P[i],P[prev])!=0)
  80.        {
  81.            prev++;
  82.            P[prev]=P[i];
  83.        }
  84.     }
  85.     count=prev+1;
  86. return count;
  87. }
  88.  
  89. void Solve(int n,Point *P, int *top, Point *S)
  90. {
  91.      int i,k,min,m;
  92.      Point t;
  93.      min=0;
  94.      for(i=1;i<n;i++)
  95.         if(P[i].y<P[min].y ||(P[i].y==P[min].y && P[i].x <P[min].x))
  96.             min=i;
  97.      t=P[0];
  98.      P[0]=P[min];
  99.      P[min]=t;
  100.      heapSort(n-1,P);
  101.      m=removeDuplicates(n,P);
  102.      k=-1;
  103.      i=0;
  104.      while(i<n && i<3)
  105.      {
  106.         k++;
  107.         S[k]=P[i];
  108.         i++;
  109.      }
  110.      for(i=3;i<m;i++)
  111.      {
  112.         while(k>=1 && direction(S[k-1],S[k],P[i])<=0)
  113.             k--;
  114.         k++;
  115.         S[k]=P[i];    
  116.      }
  117.      k++;
  118.      S[k]=P[0];
  119. (*top)=k;                       
  120. }
  121.  
  122. int main()
  123. {
  124.  int j,k,n;
  125.  Point *a;
  126.  Point *b;
  127.  FILE *in;
  128.  FILE *out;
  129.  
  130.  if ((in = fopen("inputg.txt", "rt"))
  131.        == NULL)
  132.    {
  133.       fprintf(stderr, "Cannot open input file.\n");
  134.       return 1;
  135.    }
  136.  if ((out = fopen("outputg.txt", "wt"))
  137.        == NULL)
  138.    {
  139.       fprintf(stderr, "Cannot open output file.\n");
  140.       return 1;
  141.    }
  142.  while(!feof(in))
  143.  {
  144.    fscanf(in,"%d",&n);
  145.    a=(Point *)malloc(n*sizeof(Point));
  146.    b=(Point *)malloc(n*sizeof(Point));
  147.    for(j=0;j<n;j++)
  148.       fscanf(in,"%d %d",&a[j].x,&a[j].y);
  149.    Solve(n,a,&k,b);
  150.    for(j=0;j<k;j++)
  151.       printf("%d %d \n",b[j].x,b[j].y);
  152.    printf("\n");
  153.    fprintf(out,"%d\n",k);
  154.    for(j=0;j<k;j++)
  155.       fprintf(out,"%d %d ",b[j].x,b[j].y);
  156.    fprintf(out,"\n");
  157.    free(a);
  158.    free(b);
  159.  }
  160.  fclose(in);
  161.  fclose(out);
  162.  
  163.  getch();
  164.  return 0;
  165. }
  166.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.c:3:18: fatal error: conio.h: No such file or directory
 #include<conio.h>
                  ^
compilation terminated.
stdout
copy 
Standard output is empty
https://ideone.com/vvBi4A
language:
C (gcc 8.3)
created:
7 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!