#include<X11/Xlib.h>
#include<X11/Xutil.h>
#include<stdio.h>
#include <stdlib.h>
#include <string.h>    /* strlen() */

struct point {
  int x, y;
};
char s0[10];
XColor red, blue, green, yellow, c0;
Colormap cmap;
char *itoa(int n, char *arr)
{
    int i;
    sprintf(arr, "%d", n);
    for(i = strlen(arr); i < 9; i++) {
        arr[i] = ' ';
    }
    arr[9] = '\0';
    return arr;
}

struct segment {
  struct point p1, p2;
};
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 intersect(struct segment s1, struct segment s2)
{
  if(((s1.p1.x==s1.p2.x)&&(s1.p1.y==s1.p2.y))||
     ((s2.p1.x==s2.p2.x)&&(s2.p1.y==s2.p2.y)))
  return ((turn(s1.p1, s1.p2, s2.p1)*turn(s1.p1,s1.p2,s2.p2))<=0)
     ||  ((turn(s2.p1, s2.p2, s1.p1)*turn(s2.p1,s2.p2,s1.p2))<=0);
  return ((turn(s1.p1, s1.p2, s2.p1)*turn(s1.p1,s1.p2,s2.p2))<=0)
     &&  ((turn(s2.p1, s2.p2, s1.p1)*turn(s2.p1,s2.p2,s1.p2))<=0);
}
main()
{   
   struct point p[100];
   struct point v;
   struct segment sp, sw, ss;
   Display *d;
   Window w;
   GC gc;
   Font f;
   XEvent e;
   int i, j, n, count,black, white;


   d=XOpenDisplay((getenv("DISPLAY") != NULL)?getenv( "DISPLAY"):":0");
   f=XLoadFont(d,"r14");
   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),5,5,400,400,5,
     black, white);
   XSelectInput(d,w,ButtonPressMask|ButtonReleaseMask);
   XMapWindow(d,w);
   gc=XCreateGC(d,w,0,0);
   XSetFont(d,gc,f);
   XSetLineAttributes(d,gc,1,LineSolid, CapButt, JoinMiter);
   XFlush(d);
/*
   i=1;
   XNextEvent(d,&e);
   if(e.type==ButtonPress){p[1].x=e.xbutton.x; p[1].y=e.xbutton.y;}
   XNextEvent(d,&e);
   itoa(i,s0);
   XDrawString(d,w,gc, p[i].x,p[i].y,s0, strlen(s0));
   i=2;
   while(1){
      XNextEvent(d,&e);
      if (e.xbutton.x>350) break; // The rightmost terminates 
      switch(e.type){
	 case ButtonPress:
              p[i].x=e.xbutton.x;              
              p[i].y=e.xbutton.y;              
              XDrawLine(d,w,gc,p[i].x,p[i].y,p[i-1].x,p[i-1].y);
              itoa(i,s0);
              XDrawString(d,w,gc, p[i].x,p[i].y,s0, strlen(s0));
              i++;
	      break;
	 case ButtonRelease:
	      break;
      }
   }
   n=i-1;
   XDrawLine(d,w,gc,p[n].x,p[n].y,p[1].x,p[1].y);
   XNextEvent(d,&e);
   XNextEvent(d,&e);
   XSetArcMode(d,gc,ArcPieSlice);
   XFillArc(d,w,gc,e.xbutton.x,e.xbutton.y,10,10,0,360*64);
   XNextEvent(d,&e);
   v.x=e.xbutton.x; v.y=e.xbutton.y;
   XFlush(d);
*/
   n=5;                        // new
   p[1].x=20; p[1].y=20;       // new
   p[2].x=120; p[2].y=40;      // new
   p[3].x=100; p[3].y=80;      // new
   p[4].x=140; p[4].y=60;      // new
   p[5].x=80; p[5].y=160;      // new
   v.x=80; v.y=60;

   p[0]=p[n]; p[n+1]=p[1];
   i=1;
   while(i<=n){
              XDrawLine(d,w,gc,p[i].x,p[i].y,p[i-1].x,p[i-1].y);
              itoa(i,s0);
              XDrawString(d,w,gc, p[i].x,p[i].y,s0, strlen(s0));
              i++;
   }
   sw.p1=v;
   sw.p2.x=20000; sw.p2.y=v.y;
   ss.p1.y=v.y; ss.p2.y=v.y; ss.p1.x=-20000; ss.p2.x=20000;
   XDrawLine(d,w,gc,sw.p1.x,sw.p1.y,sw.p2.x,sw.p2.y);
   printf("Keep hitting return key"); getchar();
   XSetForeground(d,gc,red.pixel);
   count=0; j=0;
   for(i=1;i<=n;i++){
      printf("i=%d ", i);
      sp.p1=p[i]; sp.p2=p[i];
      if(!intersect(sp,sw)){
        printf("Next point not on sw. ");
        sp.p2=p[j];
        if(i==j+1){if(intersect(sp,sw))count++;
                   printf("Tested with sw ");
        XDrawLine(d,w,gc,p[i].x+5,p[i].y,p[j].x+5,p[j].y);}
        else {if(intersect(sp,ss))count++;
                   printf("Tested with ss. ");
        XDrawLine(d,w,gc,p[i].x+5,p[i].y,p[j].x+5,p[j].y);}
        printf(" sp= (%d, %d)", j, i);
        j=i;
      }
      else printf("Next point on sw. sp (%d, %d) ignored. ",j, i);
   XFlush(d);
      printf("count= %d", count); 
      getchar();
   }
  printf("%d\n", count&1);
  if(count&1==1)printf("inside\n"); else printf("outside\n");
}