#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <X11/Xlib.h>
#include <X11/Xutil.h>
#include "qsort.c"
Display *d,*d1 ;
Colormap cmap;
XColor red, blue, green, yellow, c0;
Window w,w1;
GC gc,gc1;
Font f;
XEvent e;
struct point q[100000];
int original;
int white, black;
int i,m, n, k,t1;
main(){
   d=XOpenDisplay((getenv("DISPLAY") != NULL)?getenv( "DISPLAY"):":0");
   black = BlackPixel(d, 0);
   white = WhitePixel(d, 0);
   cmap=DefaultColormap(d,0);
   XAllocNamedColor(d,cmap,"red",&red,&c0);
   XAllocNamedColor(d,cmap,"green",&green,&c0);
   XAllocNamedColor(d,cmap,"blue",&blue,&c0);
   w=XCreateSimpleWindow(d,DefaultRootWindow(d),0,0,400,400,5,
   black, white);
   XSelectInput(d,w,ButtonPressMask|ButtonReleaseMask|ButtonMotionMask);
   gc=XCreateGC(d,w,0,0);
   XMapWindow(d,w);
   XFlush(d);
   printf("input n "); scanf("%d", &n);
   for (i=1; i<=n; i++){q[i].x=random()%400; q[i].y=random()%400;}
   XSetForeground(d,gc,black); 
   t1=clock();
   m=convex_hull(q,n);
   printf("time = %d millisec\n", (clock()-t1)/1000);
   printf("Keep hitting 'return' for the hull\n");
   getchar();
   for (i=1; i<=n; i++)q[i].y=400-q[i].y;
   for (i=1; i<=n; i++) {
     XSetArcMode(d,gc,ArcPieSlice);
     XFillArc(d,w,gc,q[i].x,q[i].y,10,10,0,360*64);
     XFlush(d);
   }
   getchar();
   q[m+1]=q[1];
   for (i=2;i<=m+1;i++) {
     XDrawLine(d,w,gc,q[i].x+5,q[i].y+5,q[i-1].x+5,q[i-1].y+5);
     XFlush(d);
     getchar();
   }
   getchar();
}
double angle(struct point q1, struct point q2)
{
    /*  gives angle between 0 and 360 degrees */
    int dx, dy;
    double a = 0.0;
    dx = q2.x - q1.x;  dy = q2.y - q1.y;
    if (dx != 0 || dy != 0) a = (double)dy / (double)(abs(dx) + abs(dy));
    if (dx < 0) a = 2.0 - a;
    else if (dy < 0) a = a + 4.0;
    return a*90.0;
}
int turn(struct point q0, struct point q1, struct point q2)
{ int dx1, dx2, dy1, dy2;
  dx1=q1.x - q0.x; dy1 = q1.y - q0.y;
  dx2 = q2.x - q0.x; dy2 = q2.y - q0.y;
  if (dx1*dy2 > dy1*dx2) return 1;
  if (dx1*dy2 < dy1*dx2) return -1;
  if ((dx1*dx2 < 0)||(dy1*dy2 < 0)) return -1;
  if ((dx1*dx1+dy1*dy1) < (dx2*dx2+dy2*dy2)) return 1;
  return 0;
}
int convex_hull(struct point p[], int n)
{
    /* p[1] through p[n] are vertices of a polygon */
    int i, m, min; double theta, prev;
    struct point t;
    min = 1;
    for (i=2; i<=n; i++) if (p[i].y < p[min].y) min = i;
    for (i=1; i<=n; i++) if (p[i].y==p[min].y) 
                           if (p[i].x > p[min].x) min = i;
    t = p[1];  p[1] = p[min]; p[min] = t;
    for (i=1; i<=n; i++) p[i].angle=angle(p[1],p[i]);
    for (i=1; i<=n; i++) a[i]=p[i];
    quick(1, n);
    for (i=1; i<=n; i++) p[i]=a[i];
    p[0] = p[n];
    m = 3;
    for (i=4; i<=n; i++) {
        while (turn(p[m], p[m-1], p[i]) >= 0) m--;
        m++;
        t = p[m];  p[m] = p[i]; p[i] = t;
    }
   return m;
}