#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <stdbool.h>  //true false

#define MAX(a,b) ((a) > (b) ? (a) : (b))

#define MIN(a,b) ((a) < (b) ? (a) : (b))


typedef struct{
    float x;
    float y;
}TPonto;

/********************************************************************
  direcao(pi,pj,pk) determina para que lado estaria o novo segmento
*********************************************************************/
/*
 segmento pkpj à esquerda | segmento pjpk à direita
    pk       pj           |      pj        pk
    ._______ .            |     .__________.
            /             |      \
           /              |       \
          /               |        \
         .                |         .
        pi                |          pi

*/

double direcao(TPonto pi, TPonto pj, TPonto pk){
   TPonto Vik,Vij;

   Vik.x = pk.x-pi.x;
   Vik.y = pk.y-pi.y;
   Vij.x = pj.x-pi.x;
   Vij.y = pj.y-pi.y;
   if ((Vik.x*Vij.y - Vik.y*Vij.x) <0) // <0 esquerda
      return 0;
   return 1;
}


bool onSegment(TPonto pi,TPonto pj,TPonto pk){
   if( ((MIN(pi.x,pj.x) <= pk.x) && (pk.x <= MAX(pi.x,pj.x))) && ((MIN(pi.y,pj.y) <= pk.y)&& (pk.y <= MAX(pi.y,pj.y))) )
	   return true;
   return false;
}	

/*                                     ____   ____
  Verifica a intersecção dos segmentos p1p2 e p3p4
*/
bool Intersect(TPonto p1, TPonto p2, TPonto p3, TPonto p4){
   double d1,d2,d3,d4;
   d1=direcao(p3, p4, p1);
   d2=direcao(p3, p4, p2);
   d3=direcao(p1, p2, p3);
   d4=direcao(p1, p2, p4);
   if ((d1!=d2) && (d3!=d4)) 
        return true;
   else if(d1==0 && onSegment(p3,p4,p1))
        return true;
   else if(d2==0 && onSegment(p3,p4,p2)) 
        return true;
   else if(d3==0 && onSegment(p1,p2,p3))
        return true;
   else if(d4==0 && onSegment(p1,p2,p4))
        return true;

   return false;
}	


   
int main(void){
    TPonto p1,p2,p3,p4;
    /*p1.x=5; p1.y=5;   
    p2.x=2; p2.y=7;   
    p3.x=3; p3.y=4;   
    p4.x=6; p4.y=6; */  
    
    p1.x=1; p1.y=1;   
    p2.x=10; p2.y=1;   
    p3.x=1; p3.y=2;   
    p4.x=10; p4.y=2; 
    if (Intersect(p1, p2, p3, p4)) 
       printf("\nAs arestas se cruzam\n");
    else printf("\nAs arestas não se cruzam\n");
    p1.x=10; p1.y=0;   
    p2.x=0; p2.y=10;   
    p3.x=0; p3.y=0;   
    p4.x=10; p4.y=10; 
    if (Intersect(p1, p2, p3, p4)) 
       printf("\nAs arestas se cruzam\n");
    else printf("\nAs arestas não se cruzam\n");
    p1.x=-5; p1.y=-5;   
    p2.x=0; p2.y=0;   
    p3.x=1; p3.y=1;   
    p4.x=10; p4.y=10; 
    if (Intersect(p1, p2, p3, p4)) 
       printf("\nAs arestas se cruzam\n");
    else printf("\nAs arestas não se cruzam\n");
    /*if (Intersect(p1, p4, p2, p3)) 
       printf("\nAs arestas se cruzam\n");
    else printf("\nAs arestas não se cruzam\n");*/
    
    return 0;
}